An ant that builds a highway

The cellular automata met so far update every cell at once. Rule 30 keeps a column of apparently random bits that nobody can explain, and a sandpile topples its way to a group. Christopher Langton proposed in 1986 a simpler kind of system, with a single moving agent instead of a whole row of cells. An ant stands on a grid of white squares. At each step it looks at the square it is on: on white it turns right a quarter turn, on black it turns left; then it flips the square’s colour and steps forward one square. That is the whole rule.

Langton’s interest was in what he called artificial life: the smallest rules from which behaviour that looks purposeful can arise. Two years earlier he had designed a loop of cells in a cellular automaton that copies itself, the simplest known self-reproducing structure of its kind and a relative of a program that prints its own text; the ant was the opposite experiment, a rule with no design in it at all, run to see what it would do.

The ant’s behaviour falls into three stages, and only the first is what anyone would guess. For a few hundred steps it makes small symmetric patterns. Then, for about ten thousand steps, it builds an irregular blob with no visible order at all. Then, at step 9,976 in the counting used here, it falls into a cycle of 104 steps that moves it two squares diagonally and repeats for ever, laying down a straight band that runs off to infinity. The band is called the highway.

Two theorems frame the picture. Leonid Bunimovich and Serge Troubetzkoy proved in 1992 that the ant’s path is always unbounded — from any finite starting pattern, it leaves every bounded region eventually. Nobody has proved that it always builds a highway. Every starting pattern ever tried ends on one, and the statement that this always happens, the highway conjecture, is open.

Symmetry, then none #

The first stage is short and orderly. Checking the pattern of black cells after every step for a mirror symmetry across a horizontal or vertical line, or a half-turn symmetry, about the centre of the pattern, finds twenty moments in the first 473 steps at which the pattern has one — the last at steps 472 and 473 — and none at all in the next fifteen hundred. The early patterns are small, the ant keeps returning near its start, and each return can restore a symmetry that the intervening steps broke.

After about five hundred steps the returns stop restoring anything, and the blob grows without symmetry, roughly round on average and ragged in detail. The ant’s distance from its start wanders but drifts upward slowly, the way a random walk’s does, and the number of black cells grows roughly in proportion to the number of steps. Nothing about the blob looks different at step 9,000 from step 3,000 except its size.

The step where the highway begins #

The onset can be located exactly. A highway is a cycle: once the ant is on one, its position after any step is its position 104 steps earlier moved by the same two squares diagonally. So run the ant well past the onset, read off the displacement over the last 104 steps, and walk backwards through the run to find the first step from which every later step obeys the same rule.

The answer is step 9,976 in the counting used here, where step one is the first move; other conventions for counting shift it by a step or two, and the figure usually quoted is simply about ten thousand. Before it, the ant’s distance from the start wanders up and down, and the number of black cells drifts upward irregularly. After it, both grow in straight lines: each 104-step cycle adds exactly twelve black cells and moves the ant $\sqrt8$ squares further away. The change happens at a single step. Nothing in the ten thousand steps before it gives a measurable warning — the distance had been just as large several times before, and the black count’s growth rate had been just as steady.

That abruptness is what makes the ant famous. A rule of two clauses produces, from the simplest possible start, a long stretch that looks for all the world like noise, and then order arrives without a transition. The traffic rule whose jams come from nowhere shows order and disorder side by side; the ant shows them one after the other, in a single deterministic history.

A cycle of 104 steps #

The highway’s cycle can be drawn. On the highway the ant follows a fixed tangle of 104 moves, and each repetition happens on a pattern of cells that is the previous repetition’s pattern shifted along.

Each cycle ends exactly two squares down and two to the left of where it began, facing the same way, standing on a configuration identical to the one it started from but shifted by that displacement. So the next cycle is forced to repeat the last, and so is the one after. The highway is a travelling wave of the rule — a finite pattern, together with the ant on it, that reproduces itself further along — and once the ant is on it, nothing in front of it can interfere, because the grid ahead is white.

The cycle’s arithmetic checks itself. In one cycle the ant stands on white squares 58 times and on black squares 46 times, visiting 41 different squares, some of them several times. Every white square it stands on it turns black, and every black one white, so the cycle adds $58 - 46 = 12$ black squares — the twelve per cycle that the black-cell count grows by. And every white square means a right turn and every black one a left, so the ant’s heading changes by twelve quarter turns to the right in total, three full turns, which is why it ends each cycle facing exactly the way it began.

The cycle also explains why the highway is permanent in a way the disorder before it is not. The ant on the highway never revisits the chaotic blob behind it, because it is moving steadily away. A highway could only be broken by a black cell in its path, and from an empty start there are none.

A particle among mirrors #

The ant has a second description that connects it to physics. Think of each grid cell as holding a two-sided mirror set at one of two diagonal angles, the angle given by the cell’s colour, and of the ant as a particle that travels in straight lines and is deflected by the mirror in each cell it enters. A rotating mirror that flips its angle each time it is struck turns the particle’s motion into exactly the ant’s rule. Systems of this kind — a single particle moving through a lattice of scatterers that the particle itself changes — are called Lorentz lattice gases, after the model of electrons bouncing among atoms that Hendrik Lorentz proposed in 1905, and Bunimovich and Troubetzkoy’s theorem was proved for a whole family of them.

The connection runs both ways. A particle among fixed mirrors is a billiard on a grid, whose paths can be unfolded and understood; the ant’s mirrors change as it hits them, and that feedback is what destroys every simple description. A fixed mirror arrangement can trap a particle in a closed loop for ever; the flipping mirrors provably cannot, which is the content of the unboundedness theorem in this language.

Every random start found the highway #

The highway conjecture says that the ant builds a highway from any finite starting pattern, not only the empty one. The evidence is computational, and it can be repeated.

Every one of the sixty random patterns ends on a highway, after anything from 553 to 42,175 steps, with a median of 7,162. The density of black cells in the starting square makes little visible difference: the twenty starts at each density have median onsets of 5,878, 7,837 and 9,060 steps for 10, 30 and 50 per cent black, a drift far smaller than the spread within each group, and the three ranges overlap almost entirely. Some starts reach the highway faster than the empty grid does, and some take four times as long. No property of the starting pattern that anyone has found predicts when.

The theorem Bunimovich and Troubetzkoy proved is weaker but solid. In outline, their argument is about the cells the ant visits infinitely often: if the ant were trapped in a bounded region, some cells would be visited infinitely often, and following the turns the ant must make at the outermost of them leads to a contradiction, because the ant cannot keep turning back into the region at every one. So the ant must escape. How it escapes — on a highway, or along some other unbounded path — the argument says nothing about.

Laurent Gajardo, Andrés Moreira and Eric Goles showed in 2002 that starting patterns can be designed to make the ant compute: suitable arrangements of black cells act as wires and logic gates that the ant’s path passes through, so that predicting the ant’s behaviour from a large enough pattern is at least as hard as evaluating any Boolean circuit. That is the same kind of result as Rule 110’s ability to compute anything, and it suggests that the highway conjecture, if true, is true for reasons that do not make the ant’s intermediate behaviour simple.

The ant can walk itself back #

The rule has a property that makes the disorder even stranger: it is reversible. From the grid and the ant’s position and heading at any moment, the previous moment can be reconstructed exactly.

To reverse a step, move back one square against the ant’s heading, flip the colour of the square it is now on, and undo the turn that colour would have dictated — right for white, left for black. The backward run retraces the forward one exactly and finishes on an empty grid, with the ant at its starting square facing its starting direction. No information is ever lost.

Reversibility rules out one easy explanation of the highway. In an irreversible system, many states can flow into one, so order can arise by forgetting: a pendulum with friction ends at rest whatever its start. The ant forgets nothing. Its ten thousand disordered steps are a one-to-one record of its history, and the highway is not an attractor that pulls states together but a pattern that the dynamics happens to reach and then copy for ever. Explaining why every start reaches one cannot rely on the system losing the details of where it began, which is one reason the conjecture has resisted proof.

Other ants, other worlds #

The rule generalises naturally. Give the grid more colours in a cycle, and give the ant a string of turns, one letter for each colour: the ant turns as the letter for its square’s colour says, advances the square to the next colour in the cycle, and steps forward. Langton’s ant is the string RL.

The three strings in the figure behave entirely differently. RLR grows disorder indefinitely, with no highway in sight in the steps drawn. LLRR builds a pattern with a mirror symmetry, and recovers that symmetry again and again as it grows; David Gale, James Propp, Scott Sutherland and Serge Troubetzkoy showed in 1995 that every rule string made of repeated letters in matched pairs produces bilaterally symmetric patterns infinitely often. The long string LRRRRRLLR fills a growing square almost solidly. The same two ingredients — a turn depending on colour and a change of colour — produce every kind of large-scale behaviour, and which one a given string produces has to be found by running it.

Ants with more than two colours have their own highways, of other periods and slopes, and their own open conjectures. The systematic study of these “turmites”, as they came to be called when the grid also gives the ant an internal state, is a catalogue built by exhaustive experiment, much like the elementary rules sorted into classes by watching them.

What the simulations cannot settle #

Every figure here is a computation of a deterministic process, and each one is exact for what it shows. The empty grid’s onset at step 9,976 is a fact, the 104-step cycle and its twelve new black cells are facts, and the backward run’s return to an empty grid is a fact. None of them is in doubt.

What the figures cannot settle is everything about infinitely many starts. Sixty random patches is a small sample of an infinite space, and the space includes deliberately designed patterns — like the circuits of Gajardo, Moreira and Goles — that no random sample is likely to hit. A pattern that delays the highway for a billion steps, or prevents it altogether while still letting the ant escape as the theorem requires, would not show up in any experiment of this kind unless someone were looking for it.

The highway’s direction is also unpredictable in the same way. By the symmetry of the rule, a highway can run off along any of the four diagonals, and from the empty grid, in the orientation drawn here, it heads down and to the left; from other starts it heads elsewhere, and which diagonal a given pattern picks is, like the onset, found only by running the ant until the highway appears. Mirror-image starting patterns give mirror-image histories, highways included, which is the one prediction the rule’s symmetry makes for free.

And the onsets show no pattern, which is itself a finding the figures can only report, not explain. The median of seven thousand steps and the range of a few hundred to over forty thousand describe this sample; nothing about the rule says what the distribution of onsets should be over random starts, or whether it has a finite average.

Still open: the highway conjecture #

Does Langton’s ant, started on any finite pattern of black cells, eventually build a highway? Every pattern tried says yes. The proved part is that the ant always escapes every bounded region; the unproved part is that it does so on a periodic highway rather than along some aperiodic unbounded path. The difficulty is that the ant’s behaviour before the highway is, as far as anyone can tell, irreducible: there seems to be no shortcut for predicting what it does other than running it, and the ability to build logic circuits out of starting patterns suggests that no general shortcut exists.

It joins a family of questions about simple deterministic rules that are easy to state and resist all proof — whether every Collatz orbit reaches one is the best known — and like that question, it is the kind where a counterexample would have to be a pattern so large or so special that no search has found it, while a proof would have to explain an order that nothing in the rule seems to contain.

Disorder, then order, from two rules #

An ant that turns right on white and left on black, flipping colours as it goes, wanders for 9,975 steps without visible order and then builds a highway: a cycle of 104 steps that moves it two squares diagonally and adds twelve black cells each time. Its rule is reversible, so the order is not reached by forgetting; its starting patterns can encode logic circuits, so its behaviour can be as hard to predict as any computation; and while it provably escapes to infinity from any finite start, that it always does so on a highway is a conjecture every simulation supports and no argument has reached.