Math

Cellular automata · emergence

Langton’s ant

Langton’s ant walks on an endless grid of squares: on an empty square it turns right (R), on a marked square it turns left (L); then it flips the square and steps forward.

Langton’s ant in this visualization

Langton’s ant is the simplest of a family of ants. With n colours, numbered from 0 for empty, a rule is a string r=r0r1⋯rn−1r = r_0 r_1 \cdots r_{n-1} of letters R and L, one for each colour, and Langton’s ant is RL. The ant stands on a square p facing a direction d, and one step is

k=c(p),d←d turned by rk(R: 90∘ clockwise, L: anticlockwise),c(p)←(k+1) mod n,p←p+d.\begin{aligned} k &= c(p), \\ d &\leftarrow d \text{ turned by } r_k \quad (\text{R: } 90^\circ \text{ clockwise, L: anticlockwise}), \\ c(p) &\leftarrow (k + 1) \bmod n, \\ p &\leftarrow p + d. \end{aligned}

The ant has no memory and sees only the colour under it. Here you can watch it make order, then a tangle, then a road, run it backwards, colour squares in its way and try other strings of letters.

The colours are the states of the rule. The plane has no edge and does not wrap round. The curve at the top of the panel counts the coloured squares after every step.

Starting on the empty plane facing up, the ant first makes small, tidy patterns, some of them symmetric under a half turn, as at step 473. A tangle that looks random follows for about ten thousand steps. Then, from step 9 977 on, the ant repeats the same 104 moves, each round shifted by (−2, 2), two squares left and two down. It is building a diagonal strip called the highway, and every 104 steps add exactly 12 coloured squares. Only the ant’s moves and the strip under it repeat. The tangle behind stays where it is.

A few rounds of repetition prove nothing, since the next round could run into a coloured square and turn off. So the page promises a road only after a check. After the last round, the squares it read, moved by the ant’s displacement, must show the colours those squares had before the round, and the ant must face the way it faced then. And in every later round, the squares beyond the previous round’s must be empty now and must not have been visited by any round since the checked one. Then each round meets exactly what the round before it met, so it makes the same moves, forever. The dashed line on the curve marks where the repetition starts. When a coloured square lies ahead, the page circles it and makes no promise.

For the empty plane the road is therefore proved, by computation together with this check. For RL, every board with finitely many coloured squares that has been tried ends in a road, but nobody has proved that every one does.

Every step can be undone. The ant faces the way it just moved, so the square it came from is behind it, and that square’s colour has moved one step round the cycle. One step back is

p←p−d,k=(c(p)−1) mod n,c(p)←k,d←d turned back by rk.\begin{aligned} p &\leftarrow p - d, \\ k &= (c(p) - 1) \bmod n, \quad c(p) \leftarrow k, \\ d &\leftarrow d \text{ turned back by } r_k. \end{aligned}

So the board and the ant determine the state one step earlier, and Backward runs the ant back by the rule, not by replaying a recording.

With more letters, each visit moves a square on to its next colour. Started on the empty plane, the rule keys grow very different shapes: a pattern that looks symmetric for LLRR, an almost solid square for LRRRRRLLR, a growing triangle for RRLLLRLLLRRR. How these three end is not known. LLRRRLRLRLLR does build a road, after about thirty thousand steps.

Chris Langton described the ant in 1986 as an example of artificial life.

Related

Further reading: Wikipedia: Langton's ant; Wikipedia: Turmite; Wikipedia: Cellular automaton.