Langton’s Ant Wiki

History

Christopher Langton described the ant in 1986, in a paper on studying artificial life with cellular automata. He was looking for the simplest systems that still show lifelike behaviour: patterns that build, spread and organise themselves. A year later he organised the first Artificial Life workshop at Los Alamos, which helped launch artificial life as a field.

The ant is a turmite: a Turing machine whose tape is a two-dimensional grid. It has no memory beyond the direction it faces, yet what it draws is still not fully understood almost forty years later.

The rules

Start with an infinite grid of white squares and one ant facing up. Every step:

if the square is white:  turn right 90°
else (it is black):      turn left 90°
flip the square's colour
move forward one square

That is the whole program. Its rule string is RL: the first colour (white) turns Right, the second (black) turns Left.

Three phases

Started on an empty grid, the ant always goes through the same three phases. These pictures are drawn live by this page, using the rules above.

Simplicity · step 400. Small patterns, often symmetric.

Chaos · step 6,000. An irregular blob with no visible structure.

Order · step 12,000. The highway heads off diagonally.

The highway

At step 9,977 the ant falls into a cycle of 104 steps. At the end of each cycle it is exactly two squares further along a diagonal, and the strip behind it is the same as before. It repeats this forever, laying down a straight band called the highway.

The lab’s simulation reproduces both numbers: from step 9,977 onward, every 104 steps move the ant by (−2, +2) and add exactly 12 black squares.

The highway seems to be an attractor. Every finite starting pattern anyone has tried eventually produces one. Nobody has proved this is always true.

What’s been proven

The ant never stays put: Whatever the starting grid, the ant’s path is unbounded: it can’t stay inside any finite region forever. This is known as the Cohen–Kong theorem, and it appears in Bunimovich and Troubetzkoy (1992).
The ant can compute: Gajardo, Moreira and Goles (2002) showed how to lay out a starting grid so that a single ant’s path calculates any Boolean circuit. So predicting what the ant will do from an arbitrary start is a hard computational problem.
Still open: Whether every finite starting pattern eventually leads to a highway.

More colours

Greg Turk and Jim Propp extended the ant to more than two colours. Each colour has its own turn, and when the ant leaves a cell it moves that cell on to the next colour in the cycle. The rule is named by its list of turns, one per colour, so the classic ant is RL: on colour 1 (white) turn right, on colour 2 (black) turn left.

look up the turn for this cell's colour, and turn
move the cell on to the next colour (the last wraps round to white)
move forward one cell

The same idea works on a hexagonal grid, where each cell has six neighbours and the ant can turn by any multiple of 60°: N (no turn), R₁ (60° clockwise), R₂ (120° clockwise), U (180°), L₂ (120° anticlockwise) and L₁ (60° anticlockwise).

Ants like these, and their relatives with more than one internal state, are called turmites, short for “Turing machine termites”. The behaviours that keep turning up are highways, chaotic growth and spirals, and all three appear below.

Ant by ant

Every picture is drawn live by this page from a blank grid. The colour strip shows each rule’s cycle: a cell starts white, and each visit moves it one colour to the right, wrapping back to white. The letter next to each colour is the turn the ant makes there. Facts marked measured come from running the same rules the lab runs. All nine ants run in the lab: pick one under Rule.

12,000 steps

RL Square · 2 colours · the classic

Simple patterns for a few hundred steps, then thousands of steps of chaos, then a highway that never ends.

Highway: from step 9,977 the ant repeats a 104-step cycle that moves it 2 squares diagonally and adds exactly 12 black squares each time (measured).

Every finite starting pattern anyone has tried ends in this same highway, but nobody has proved that it always will.

200,000 steps

LLRR Square · 4 colours

Grows as a compact, symmetric blob.

Why symmetric: its name, read round in a circle, is made of pairs of identical letters (LL, RR). That is enough to guarantee that the pattern is mirror-symmetric again and again, forever; the proof uses Truchet tiles. RLLR qualifies too, because the R at the end wraps round to pair with the R at the start.

In its first 60,000 steps, LLRR’s pattern is exactly mirror-symmetric at 1,878 different moments, spread through the whole run (RLLR: 1,367). RLR, which has no such pairs, manages it only 4 times (measured).

200,000 steps

RLR Square · 3 colours

Grows chaotically, in a ragged blob with no visible structure.

Open question: nobody knows whether it ever builds a highway. The lab found no repeating cycle up to 2,000 steps long anywhere in its first 2 million steps (measured).

It spreads slowly: going from 100,000 to 1.6 million steps, 16 times longer, only takes its width from 120 to 258 squares (measured).

200,000 steps

LRRRRRLLR Square · 9 colours

Fills space in a solid square around itself, with diagonal streaks running through it.

Packed: 96–98% of the cells inside its bounding square are coloured, and the square stays square as it grows: 87 squares wide at 50,000 steps, 180 at 200,000, 437 at 800,000 (measured).

Each time the step count goes up 4×, the side roughly doubles, so the filled area grows in step with the number of steps.

60,000 steps

LLRRRLRLRLLR Square · 12 colours

Builds a convoluted highway: a thick, knotted band instead of RL’s neat diagonal strip.

Its cycle: from about step 29,890 the ant repeats a cycle of 1,968 steps, and each cycle moves it 16 squares in a straight line, along a row rather than a diagonal (measured).

That cycle is almost 19 times longer than the classic ant’s 104 steps.

60,000 steps

RRLLLRLLLRRR Square · 12 colours

After a chaotic start, builds a filled triangle that keeps growing and moving.

When it starts: Wikipedia puts the switch at around 15,900 steps. In the lab its bounding box grows by only 3 squares between steps 10,000 and 15,000, then steadily: 39 × 49 at 16,000, 92 × 102 at 40,000, 136 × 146 at 80,000 (measured).

300,000 steps

L₂NNL₁L₂L₁ Hexagonal · 6 colours

Grows into a lumpy blob full of round holes.

Two of its colours are N, “no turn”, so the ant often runs straight through cells.

Not quite as advertised: Wikipedia describes it as growing circularly, with a picture of a ring. From a blank grid, the lab never forms a clean ring, even after 3 million steps (measured); the published picture probably came from a different set-up.

200,000 steps

L₁L₂NUL₂L₁R₂ Hexagonal · 7 colours

Grows in a spiral, with the hexagonal grid giving it a hexagonal outline.

Steady growth: about 3 cells end up coloured for every 10 steps: 30,094 cells after 100,000 steps, 481,399 after 1.6 million. Its width doubles each time the steps go up 4× (299 → 593 → 1,160) (measured).

200,000 steps

R₁R₂NUR₂R₁L₂ Hexagonal · 7 colours

The previous ant with every left turn swapped for a right turn, so from the same start it draws the same spiral, flipped.

Exact mirror: after 200,000 steps both have 60,186 coloured cells, and their ants stand at mirror-image positions, (182, 4) and (182, −4) (measured). Wikipedia lists it as an “animation”, which probably describes how its picture was made.

Odd facts

Every ant can run backwards: Given where the ant stands and which way it faces, its previous step is fully determined: step back, return that cell to its previous colour, and undo the turn that colour calls for. So no information is ever lost. Running RL, RRLLLRLLLRRR and L₁L₂NUL₂L₁R₂ forward 100,000 steps and then back again returns a blank grid with the ant at the start, facing its first direction, every time (measured).
Swap L and R, get a mirror image: Flipping every turn reflects the whole run, which is why the two spiral ants above are twins. The same goes for square ants: LR draws the classic ant’s pattern, mirrored.
The highway is tidy: The classic highway adds exactly 12 black squares every 104 steps, so far out along it the number of black squares grows by a steady 12 per cycle (measured).

How the lab runs it

Storage. The grid is split into 256 × 256 tiles of bytes, one byte per cell holding its colour, created only where the ant has been. Hex cells use the same tiles: rows stay rows, and odd rows count as shifted half a cell to the right. Zoomed in, they’re drawn as real hexagons; zoomed out, where a cell is only a few pixels, the fast pixel drawing takes over. A step is a lookup, a flip and a move, so 5 million steps take about a tenth of a second.
Drawing. Each frame copies just the visible squares into one image the size of the screen. When zoomed out, a screen pixel turns black if any square it covers is black, so the highway stays visible at any zoom.
Speed. The simulation gets a fixed slice of each frame. If your device can’t keep up with the speed you chose, the lab runs as fast as it can and shows the real rate next to the slider.

Sources

Langton, C. G. (1986). “Studying artificial life with cellular automata.” Physica D 22(1–3): 120–149. doi:10.1016/0167-2789(86)90237-X
Bunimovich, L. A. & Troubetzkoy, S. E. (1992). “Recurrence properties of Lorentz lattice gas cellular automata.” Journal of Statistical Physics 67(1–2): 289–302. doi:10.1007/BF01049035
Gajardo, A., Moreira, A. & Goles, E. (2002). “Complexity of Langton’s ant.” Discrete Applied Mathematics 117(1–3): 41–50. doi:10.1016/S0166-218X(00)00334-6
Gale, D., Propp, J., Sutherland, S. & Troubetzkoy, S. (1995). “Further travels with my ant.” The Mathematical Intelligencer.
Langton’s ant, Wikipedia.