Langton's Ant
Watch a two-rule ant build order out of chaos. Run the classic RL turmite or write your own multi-colour rule string, adjust speed, and export the pattern as a PNG.
2 colours — cell state → turn
Two rules, and that is the whole program
Chris Langton described this automaton in 1986. An ant sits on a grid of white cells facing one direction, and repeats two instructions forever:
- On a white cell: turn 90° right, flip the cell to black, move forward one square.
- On a black cell: turn 90° left, flip the cell to white, move forward one square.
There is no randomness, no lookahead, and no memory beyond the colour under the ant. Everything you see on the canvas is those two lines executed a few hundred thousand times.
Three phases, and nobody can explain the third
Steps 1–500
Simplicity
Small, near-symmetric shapes. The pattern looks like it might repeat.
Steps 500–10 000
Chaos
A pseudo-random blob with no visible structure, growing in every direction.
Step ~10 000 onward
The highway
A 104-step cycle locks in and the ant builds a diagonal road, forever.
The highway is the famous part. After roughly ten thousand steps of apparent noise, the ant falls into a repeating sequence of 104 moves that displaces it two cells diagonally and leaves an identical strip of pattern behind. It never leaves that cycle.
What makes it interesting is that nobody has proved it has to happen. Every starting configuration ever tested — including grids seeded with arbitrary black cells — eventually produces a highway, but no proof exists that this is inevitable. It remains an open problem, and it is a striking demonstration that a completely deterministic two-line rule can be beyond current mathematics to predict.
What is proved is Cohen's theorem: the ant's trajectory is always unbounded. It can never stay confined to a finite region, no matter what you start it with.
Rule strings and multi-colour turmites
Generalising is easy: use n colours instead of two and give each one a turn direction. A rule string like LLRR means state 0 turns left, state 1 turns left, state 2 turns right, state 3 turns right — and each visit advances the cell to the next state, cycling back to 0. The classic ant is simply RL.
These generalisations are called turmites, and the variety is startling for such a small rule space. Some fill space chaotically forever. Some build highways in a few thousand steps. Some grow symmetric, almost organic-looking shapes — LLRR produces a growing cardioid, and RRLLLRLLLRRR fills a clean triangle.
With 2ⁿ rule strings of length n, there are over four thousand distinct rules at length 12 alone. The random button samples that space; most produce chaos, and a minority produce something structured. There is no known way to tell which from the string alone short of running it.
| Rule | Behaviour |
|---|---|
| RL | Chaos, then a highway at about 10 000 steps. The original. |
| RLR | Grows chaotically with no highway found in any tested run. |
| LLRR | Symmetric, cardioid-shaped growth — visually the most orderly. |
| LRRRRRLLR | Fills a rough square region with textured interior. |
| RRLLLRLLLRRR | Builds a clean growing triangle. |
It is a universal computer
In 2000, Gajardo, Moreira, and Goles proved that Langton's ant is Turing complete. Their construction encodes a boolean circuit into the initial arrangement of black cells; the ant, following its two rules, evaluates it. Anything a computer can compute, this ant can compute, given the right starting grid.
That places it alongside Conway's Game of Life and Rule 110 as an example of computational universality emerging from a trivially small rule set. The interesting part is not that a computer can be built out of it, but how little machinery it takes: one moving head, one bit per cell, two instructions.
It also explains why the highway question is hard. Predicting the long-term behaviour of a universal system is equivalent to solving the halting problem for it — so a general answer for arbitrary starting configurations cannot exist.
Implementation notes
- State fits in a byte. The grid is a flat Uint8Array of cell states; direction is 0–3 and turning is (dir + turn) & 3.
- Only one pixel changes per step. The canvas keeps a persistent ImageData buffer and writes a single RGBA quad per step, then blits once per animation frame — which is why 50 000 steps per frame stays smooth.
- The grid is a torus. An ant leaving the right edge reappears on the left. Real Langton's ants live on an infinite plane; the wrap notice appears once that boundary matters.
- The red dot is the ant. It is painted on top of the blit each frame and never enters the buffer, so it leaves no trace in the exported PNG.