Langton's Ant: How Two Rules Build a Highway

Two rules, no memory

Christopher Langton introduced this in 1986 as a thought experiment in artificial life. The setup: an infinite grid of cells, each white or black, and a single ant standing on one cell, facing one of four directions. At every step it applies exactly two rules, in order: on a white cell, turn 90° right; on a black cell, turn 90° left. Then it flips the colour of the cell it's standing on and moves forward one step.

if cell[x][y] == WHITE: dir = turnRight(dir)
else:                   dir = turnLeft(dir)
cell[x][y] = flip(cell[x][y])
(x, y) = stepForward(x, y, dir)

That's the whole specification. The ant carries no internal memory beyond its position and heading — it reacts only to the single cell it's currently standing on. Everything that follows, including behaviour nobody has fully explained, comes from those three lines.

Three phases: order, chaos, highway

Starting from a blank grid, the ant's trajectory splits into three sharply different regimes. For roughly the first 500 steps it builds small, near-symmetric patterns, almost crystalline. Then, for the next several thousand steps, it appears to wander unpredictably — the visited region grows raggedly with no visible structure at any scale. Then, without warning, at around step 9,978 for the standard blank-grid starting condition, it locks into a 104-step cycle that carries it two cells diagonally every cycle, and repeats forever, as far as anyone has ever computed. That's the highway.

The highway conjecture — still unproven

The obvious question — does every starting configuration eventually build a highway? — is called the highway conjecture, and as of 2026 it remains open. Exhaustive computer search covering billions of initial configurations has never found a counterexample, but there is no general proof. What is known for the blank-grid case: the highway's 26-cell footprint repeats every 104 steps, displacing the ant by exactly (2,−2), and its direction is fixed the moment the ant's very first turn breaks the grid's fourfold symmetry. Change a single cell in the starting configuration and the highway can appear in a completely different orientation, or be delayed by hundreds of thousands of steps — a form of sensitivity to initial conditions, though the system itself is fully deterministic and not chaotic in the dynamical-systems sense.

Turmites: generalising the ant

Rudy Rucker coined Turmite (Turing + termite) for the general family: k possible cell colours instead of two, s possible internal ant states instead of one, and a transition table mapping (state, colour) to (new state, new colour, turn). Langton's original ant is the simplest Turmite — k=2, s=1 — written compactly as the rule string RL (turn Right on colour 0, Left on colour 1). Extend the string: RLLR grows a slow, near-fractal boundary; LLRR produces fast irregular growth with no observed highway; longer strings like LRRRRRLLR produce billiard-ball-like periodic structures with periods in the thousands. Turmites with two or more internal states are proven Turing complete — they can compute anything, given a suitable initial tape — which places these machines right at the boundary of computational universality; the plain single-state ant is not known to be, precisely because its eventual periodicity would rule out unbounded computation, if the highway conjecture holds.

Frequently asked questions

Try it live

Everything above runs in your browser — open Langton's Ant and watch chaos give way to a perfectly periodic highway, then swap in a different turmite rule string and see how radically the pattern changes. Nothing is installed, nothing is uploaded.