Langton's Ant
Two rules and one ant. For about ten thousand steps it makes a mess. Then it builds a road and walks down it forever. Nobody has been able to prove that it always must.
The rules
The ant sits on a square grid, facing one of four directions. At each step:
- if the square is white, turn 90° right; if it is black, turn 90° left;
- flip the colour of the square;
- move forward one square.
That is the entire specification. It was introduced by Christopher Langton in 1986 as one of the simplest possible "artificial life" systems - and it is a Turing machine, with the grid as its tape.
The three phases
Every run of the classic ant goes through the same three phases, which is itself remarkable given how simple the rule is:
- Simplicity (roughly the first 500 steps)
- The ant produces small, often symmetric patterns. You can follow what it is doing.
- Chaos (roughly steps 500 to 10,000)
- A large, irregular blob with no discernible structure. This phase resists every attempt at description.
- The highway (from about step 10,000 onwards)
- Abruptly, the ant locks into a cycle of 104 steps that displaces it two squares diagonally. It then repeats that cycle forever, building a perfectly regular diagonal corridor out to infinity.
Every starting configuration ever tested - including grids seeded with arbitrary black squares - eventually produces a highway. This is Langton's Ant conjecture, and it is unproved. What has been proved (the Cohen-Kong theorem) is that the ant's trajectory must be unbounded: it can never stay in a finite region forever.
Turmites
Generalise the ant by giving it more colours and a longer turn sequence and
you get a turmite. Write the sequence as a string of
L and R: the classic ant is
RL, meaning turn right on colour 0, left on colour 1. Longer
strings use more colours, cycling through them as the ant visits.
Some of the well-known ones, all available in the panel:
| Sequence | Behaviour |
|---|---|
| RL | The classic ant. Chaos, then a highway. |
| RLR | Grows chaotically without ever settling into a highway. |
| LLRR | Grows symmetrically and produces intricate bilateral structure. |
| LRRRRRLLR | Fills space with a rough square whose edges keep expanding. |
| LLRRRLRLRLLR | Builds a convoluted, near-cardioid outline. |
| RRLLLRLLLRRR | Produces a striking filled triangle. |
You can type any string of Ls and Rs into the panel. Anything up to twelve characters produces something worth looking at; most sequences fall into either "grows a blob" or "grows a symmetric ornament", and a small minority do something genuinely surprising.