Chapter 04 · Order after chaos
The ant and the highway
An ant on a grid follows a rule you can learn in ten seconds. For ten thousand steps it makes a mess. Then it starts building a road, and it never stops.
In 1986 Chris Langton, a computer scientist working out what "artificial life" might mean, described a handful of tiny machines living on grids. One of them is now called Langton's ant. It is about as simple as a program can be, and forty years later it still holds a question nobody has answered.
The rule
Take a grid of squares, all white. Put an ant on one square, facing up. At each step the ant looks at the square it is standing on:
- On a white square, it turns 90° to the right.
- On a black square, it turns 90° to the left.
Then it flips the colour of that square and moves forward one square. That's all. There is no randomness anywhere, so the same start always gives exactly the same run.
Three stages
Simple. For the first few hundred steps the ant draws small, tidy shapes, often symmetric. Step through them one at a time and you can follow its logic and predict the next move.
Chaos. Then the tidiness goes. The ant builds a ragged, growing blob with no structure you can see, doubling back over its own trail and erasing parts of it. Nothing about the blob tells you it is about to change.
The highway. After about ten thousand steps (9,977, to be exact) the ant falls into a cycle. It makes a sequence of 104 moves that leaves it two squares further along a diagonal, facing the same way, with the same pattern of black squares around it, just shifted. Then it does the same 104 moves again, and again. The striped diagonal band it leaves behind is called the highway.
On an infinite empty grid, the highway goes on forever. That part is not a guess: each cycle only ever runs into fresh white squares, where it does exactly what it did last time. The marker in Figure 1 shows where the cycle started. The figure checks, as the ant runs, whether its recent moves repeat the moves of 104 steps earlier, shifted along the diagonal, and raises the marker once that has held for four full cycles.
The rule says nothing about diagonals, cycles or roads. All of that comes out of the walking.
What is proven
Could the ant, from some starting pattern, get stuck going round in a small region forever? No. In 1992 Leonid Bunimovich and Serge Troubetzkoy proved that, whatever squares start out black, the ant's path is unbounded: it always eventually travels arbitrarily far from where it started. The proof is short. Since the ant turns on every step, its moves alternate between horizontal and vertical, and that constrains how it can enter each square enough to rule out staying trapped.
Going arbitrarily far is much weaker than building a highway. Whether every finite starting pattern eventually leads to a highway is an open problem, meaning nobody has settled it. Every finite pattern anyone has tried has ended in the same 104-step highway, but nobody has a proof that they all do.
You can add to the experiments in Figure 2. Paint black squares before or during a run, or start from a patch of random noise.
The time it takes varies widely. A random patch might give a highway after two thousand steps or after forty thousand. A highway that runs into something you painted usually breaks, and the ant goes back to chaos for a while. Then, as far as anyone has seen, it builds another one somewhere else. If the ant reaches the edge without settling down, that is not a counterexample: the grid is only 160 squares wide, and the open question is about an infinite one.
More colours
The ant generalises easily. Give squares more than two colours, cycling through them in order, and give each colour its own turn. Write the rule as a string of letters, one per colour: Langton's ant is RL, "turn right on colour 0, left on colour 1", and LLRR has four colours. Greg Turk and Jim Propp both explored this family. These are sometimes called generalised ants, the simplest members of a wider family called turmites.
Some of these rules grow patterns with perfect symmetry. Some produce chaos that, as far as anyone has run them, never resolves. Some build highways of their own, with different shapes and much longer periods than 104. You can't tell which by looking at the letters.
A few to try. LLRR grows a shape that keeps returning to exact mirror symmetry. RLR grows a chaotic blob. LRRRRRLLR fills in a square around itself. RRLLLRLLLRRR builds a solid triangle that crawls across the grid as it grows. LLRRRLRLRLLR spends about thirty thousand steps in chaos and then builds a broad, intricate highway that repeats every 1,968 steps.
You have to run it
You know everything about Langton's ant. The rule fits on a sticky note, and there is no hidden state and no noise. Still, if someone asks when the highway starts, the only known way to answer is to run the ant for 9,977 steps and watch. Nobody knows a formula that takes the rule and hands you that number. Change one starting square and the number usually changes, in ways nobody can foresee.
The sandpile is unpredictable because it is huge and poised on the edge of collapse. The ant is unpredictable even though it is one creature following one rule, because what it does next depends on everything it has done before. There is some evidence that no general shortcut exists. In 2002 Anahí Gajardo, Andrés Moreira and Eric Goles showed that, from a suitably prepared starting grid, the ant's trail can be made to compute any Boolean logic circuit, the kind of on–off logic a computer chip is built from. Predicting the ant in general is therefore at least as hard as predicting what an arbitrary circuit will output.
Stephen Wolfram calls this computational irreducibility: a process whose outcome can't be found any faster than by carrying the process out. That is very hard to prove for any particular system, and nobody has proved it for the ant. But the ant is as clean an illustration of the idea as there is. Knowing the rule completely does not tell you what it will do.
The honest caveats
Every grid here is finite, so these figures show only the start of a story the mathematics tells about an infinite grid. The highway detector checks the ant's recent moves. It is not a proof, and it only knows about the 104-step highway. The step 9,977 is for an empty grid. On any other start the onset is usually different, and the highway can point along any of the four diagonals.
And the central claim of the chapter is an observation, not a theorem. In every experiment anyone has published, the ant ends up on a highway. That might hold for every finite start, or fail on some pattern nobody has tried. For a rule this simple, nobody knows.
Try this
Press Pause in Figure 1 just after the highway marker appears, then press Step 104 times. Watch the ant trace the same little dance, two squares further along, every time. Then go to Figure 2, press Clear, paint a solid black wall right across the grid, and press New ant. See whether the highway can get through.