A two-rule automaton that wanders chaotically for 10,000 steps, then suddenly builds a highway to infinity.
Langton (1986): an ant on an infinite white grid follows two rules. For ~10,000 steps it wanders chaotically, then suddenly locks into a diagonal highway that extends forever. Why this happens is unknown.
On white: turn right 90°, flip to black, step forward. On black: turn left 90°, flip to white, step forward. No randomness, no memory.
The generalized $k$-color update is shown as a compact recurrence in the figure.
Figure 1. Langton's Ant on an initially blank grid. The first few hundred steps create a small symmetric pattern, then chaos.
Around step 10,000, the chaos resolves. The ant lays down a repeating diagonal stripe two cells wide, extending to the upper-right. Every 104 steps, the pattern repeats exactly, shifted two cells diagonally.
Figure 2. The same ant, with fast-forward. After the chaotic transient, the highway emerges at roughly step 10,000. Each 104-step cycle extends the highway by two cells diagonally.
The highway isn't a fluke of initial conditions. Starting on a blank grid, a single black cell, or random noise — in every known case, after some transient, the ant produces a highway.
Langton generalized the ant to k colors with a rule string of L/R characters, one per color. The ant turns as the character at the current color says, then flips the cell to the next color.
RL is the classic ant. LLRR means turn left on colors 0–1 and right on colors 2–3.
Figure 3. Generalized Langton's Ant. Each character in the rule string assigns a turn direction to a color.
Whether Langton's Ant always produces a highway is an open problem. No counterexample, no proof.