A road where nobody overtakes

Eight rules and a triangle introduced the 256 elementary rules as a census of behaviours: some freeze, some repeat, some draw Pascal’s triangle, one draws chaos. The rule that computes found one of them able to run any program. Both essays asked what a rule does. This one asks what a rule keeps — whether some quantity survives every step unchanged — and finds that almost no rule keeps anything, and that one of the few that do is a traffic model.

Rule 184 is the rule in question. Read its eight cases and it says one thing: a $1$ with a $0$ to its right moves into that $0$; a $1$ with a $1$ to its right stays put; everything else follows. Call each $1$ a car and each $0$ an empty stretch of road, all on a single lane with no overtaking, and rule 184 is traffic in the simplest form it can take.

A rule that keeps its cars #

Every step of rule 184 moves some cars and moves none out of existence. A car moves only into an empty cell, and a cell never receives two cars in one step, because a car can only come from the cell directly behind. So the number of $1$s on the ring is the same after every step, and the figure checks it on every row.

That sounds like a small thing, and it is rare. Almost every elementary rule changes how many $1$s there are: rule 90 grows a single cell into Pascal’s triangle in two colours, rule 110 grows structures from nothing, rule 0 wipes everything out. Asking which rules keep their count on every ring, from every starting row, is a finite search, and it gives a short list.

Three of the five are trivial. Rule 204 copies each cell to itself; rules 170 and 240 shift the whole row one place, so nothing ever meets anything. The remaining two are rule 184 and its mirror image, rule 226, in which cars drive left instead of right. These are the only two elementary rules in which $1$s interact and are still conserved, and in both the interaction is the same: a car cannot move into an occupied cell.

There is a general reason conservation is so restrictive. If a rule keeps the number of $1$s, the change at each cell must be what flows in from the left minus what flows out to the right, with the flow across each boundary decided by the cells beside it. For rule 184 the flow across the boundary after cell $i$ is $1$ exactly when cell $i$ holds a car and cell $i + 1$ is empty — a car crossing. Written that way, the rule is a conservation law, the discrete form of the equation that says a quantity is neither created nor destroyed but only moves, and it is that form that makes it a model of anything that moves without being created: cars, particles, a fluid in a pipe.

A queue dissolves from its front #

Start the road with every car in a single block and the mechanics of a jam become visible.

The jam dissolves from its front, one car per step, and its rear end stays put until there is nothing left behind it. The cars that have left travel as a stream with alternating cars and gaps, because each car leaves one step after the car ahead of it, which by then has moved one cell on — so the gap between them is exactly one cell. That stream is the densest arrangement in which every car can move, and its density is one half.

The front of the jam, meanwhile, is moving backwards. It starts at the block’s front car and one step later it is one cell further back, where the next car is now the front. A jam, in other words, is a region that travels against the traffic at one cell per step — the same backward-travelling wave every driver has met on a motorway, where the queue is at a fixed place on the road only because cars enter at its back as fast as they leave its front.

Half density is a sharp line #

Put the cars down at random and ask whether the jams will all clear. The answer depends on the density, and it changes abruptly at one half.

Below one half, every jam dissolves, and on a ring it does so within one lap. The reason is that the free-flowing pattern — car, gap, car, gap — needs one gap per car, and below one half there are more gaps than cars, so there is room for every car to move eventually. Above one half there are fewer gaps than cars, and at every step some car must have a car ahead of it. The count is exact: with $k$ cars on $n$ cells and $k > n/2$, at least $2k - n$ cars are stopped at every step, however long the road runs. In the figure that is $2 \times 84 - 120 = 48$, and the last row has exactly $48$.

There is a symmetry behind the half. Swap every car for a gap and every gap for a car, and reverse the direction. A gap in rule 184 moves one cell left whenever there is a car behind it to take its place, so the gaps obey rule 184 driving the other way. Dense traffic of cars is sparse traffic of gaps. Everything true below one half has a mirror statement above it, with cars and gaps exchanged, and one half is the only density that is its own mirror.

The fundamental diagram, measured exactly #

Traffic engineers summarise a road by one curve: the flow of cars past a point per unit time, against the density of cars. For rule 184 that curve can be measured exactly.

The curve is a tent. Below one half every car moves every step once the jams have cleared, so the flow per cell is the density itself. Above one half every gap moves every step, by the symmetry, so the flow is the density of gaps, $1 - \rho$. The maximum, one half, is at density one half, where cars and gaps alternate perfectly and every car and every gap moves at once.

This is the simplest possible fundamental diagram, and its shape is the qualitative one measured on real motorways: flow rises with density up to a critical point and falls beyond it, and the falling branch is where jams live. Real roads have a smoother peak and a scatter of measurements on the congested side, and adding randomness to rule 184 — cars that sometimes hesitate — produces both, which is the step Nagel and Schreckenberg took in 1992 with a model that has been a standard tool of traffic simulation since. Rule 184 is its deterministic skeleton, with a single speed and no hesitation.

Reading a jam’s speed off the curve #

The fundamental diagram does more than summarise the road. Its slope predicts how disturbances travel, and the prediction can be checked against the pictures above.

In 1955 Lighthill and Whitham, and independently Richards, treated traffic as a fluid whose density $\rho$ and flow $q(\rho)$ are related by the fundamental diagram, and whose cars are conserved. Conservation says that the density at a point changes by the difference between the flow in and the flow out, and from that alone it follows that a small change in density travels along the road at speed $dq/d\rho$ — the slope of the flow curve. On the rising branch of rule 184’s tent the slope is $+1$: a disturbance in light traffic moves forward at the speed of the cars, which is why the stripes in the first picture are all parallel. On the falling branch the slope is $-1$: a disturbance in dense traffic moves backwards at one cell per step. That is the backward drift of every jam in the dense picture, predicted from the shape of a curve without looking at a single car.

The boundary between a free-flowing region and a jammed one is a shock, a place where density jumps, and its speed is the slope of the chord between the two points of the diagram on either side. A jam of density $1$ meeting free traffic of density $\tfrac12$ has a shock speed $(0 - \tfrac12)/(1 - \tfrac12) = -1$, backwards — which is exactly the queue in the block picture, its front retreating one cell a step. The same equations, written for a continuous density, are the inviscid Burgers equation of fluid mechanics, and rule 184 is a standard discrete model of it: its jams behave as Burgers’ shocks, and its dissolving queues are Burgers’ rarefaction fans.

That a byte-sized rule should reproduce the equation physicists use for shock waves is the kind of connection this subject keeps producing, and it has a single cause. Both are statements that something is conserved and moves with a speed set by how crowded it is; everything else is detail. The models that route traffic through a network, such as the paradox where an extra road slows everyone, treat the road as a pipe with a cost; this one looks inside a single pipe, and finds a fluid.

Right at one half, jams die slowly #

At densities away from one half the jams clear, or settle, quickly. At exactly one half something slower happens.

At density one half there are exactly as many gaps as cars, so every jam can in principle dissolve — but only by pairing each of its cars with a gap, and the gaps that could serve may be far away. The rate at which jams disappear turns out to fall off like one over the square root of time, and the reason is a random walk. Read the starting row cell by cell and step up at each car and down at each gap: at density one half this is a walk that ends where it began. A jam that survives to time $t$ corresponds to a stretch of the walk that climbs a long way before returning, and such excursions become rare exactly as the chance that a walk has not yet come home does, like $1/\sqrt t$. The critical density of a deterministic rule, started at random, inherits its slowness from the statistics of a coin.

That slow decay is the signature of a phase transition in the physical sense. Below the critical density the system relaxes to free flow in a time that stays bounded as the road grows; above it, to a permanently congested state; at the critical point itself the relaxation has no fixed time scale at all, only a power law. The same structure — a sharp change of state at one parameter value, with slow, scale-free behaviour exactly there — appears in the moment a giant component emerges in a random graph, and in every system physics calls critical.

The minority ends up alone #

There is one more thing the pictures show, and it looks like a detail until it is put to use. Look at the last rows of the first and third figures. Below half density every car ends up with an empty cell ahead of it — no two cars are adjacent. Above half density every gap ends up with a car on each side — no two gaps are adjacent. In both cases the value in the minority ends up isolated, surrounded on both sides by the majority value, and the value in the majority is the only one that ever appears in runs of two or more.

That is exactly what the counting forces. With fewer cars than gaps, the free-flowing state has no two cars touching, and more gaps than cars means some gaps must be adjacent. With more cars than gaps the roles reverse. After a lap, then, rule 184 has sorted the ring into a shape in which the majority value is recognisable locally: it is whichever value appears doubled.

A cell cannot count the whole ring. It sees three cells. But after rule 184 has run, three cells are enough to see which value is doubled nearby, and a rule that simply takes the majority of each cell and its two neighbours — rule 232 — would then spread the doubled value and erase the isolated one. So the traffic rule has done something that looks like computation rather than physics: it has turned a global question, which value is in the majority, into a local one. Whether that trick works in general, and why no single rule can do it by itself, is the next question up this path, and it has a sharper answer than one might expect.

What the pictures cannot show #

An infinite road. Every figure is a ring, so cars that leave on the right re-enter on the left and every claim about “eventually” is a claim about a finite system. On an infinite road the density is a limit rather than a count, and statements such as “every jam dissolves” become statements that hold with probability one for a random start, which need a proof rather than a run.

Why exactly five rules conserve. The search checked every rule on every configuration of rings up to eight cells. A rule that conserved on all of those and failed on some larger ring would have been missed; that no such rule exists follows from the flux form of conservation, which depends only on the three cells a rule reads, and which the search is consistent with rather than a proof of.

The square-root law. The relaxation figure shows a curve falling more slowly than the others and is consistent with $1/\sqrt t$; a thousand steps on one ring cannot distinguish that power from a nearby one. The law comes from the random-walk argument, not from the picture.

Still open: how much traffic a local rule can model #

Rule 184 is exactly solvable, and nearly everything about it can be computed: its flux, its relaxation, the distribution of its jams. Models with several speeds, with randomness, or with more than one lane mostly cannot, and whether their fundamental diagrams have genuinely sharp transitions or only steep smooth ones is in several cases still argued over. The broader question — which conserved quantities a local rule can have, and what they force — has a classical answer for one dimension and one conserved number, and becomes difficult quickly beyond it.

There is also a question this rule raises about computation rather than traffic. Rule 184 gathers the cars on a ring into a regular pattern of car and gap whenever there are few enough of them, which means it is, in effect, measuring whether cars or gaps are in the majority. The essay on counting votes turns that observation into a question: can any local rule decide which value is in the majority on a ring? No single rule can — and rule 184, followed by one other rule, can.

One conserved quantity, and everything that follows #

Rule 184 has one property that 251 of the 256 elementary rules lack, and that it shares only with its mirror image and three rules that do nothing interesting: it never creates or destroys a $1$. From that single invariant come a reading of the rule as traffic, a queue that dissolves from its front at one car per step, a flow curve that is exactly $\min(\rho, 1 - \rho)$, a transition at half density where the gaps and cars trade places, and a critical slowing at that density governed by a random walk.

None of it needed to be put in. The rule is a byte, eight cases each giving one bit. What made it a model of something was noticing what it keeps.