Langton's Ant

How to use it

Press Play and watch a single ant on an empty grid. At every step it looks at the colour of the cell it stands on, turns, flips the colour of that cell and moves one cell forward. For a few thousand steps the picture grows into a messy blob that looks random. Then, after roughly 10,000 steps, the ant suddenly builds a straight diagonal road and walks away along it. That road is the highway, and the Highway readout tells you when the page has recognized it.

The grid wraps around: leaving at the right edge brings the ant back on the left, and the same at the top and bottom. A highway therefore comes around again and eventually runs into the old mess, so larger grids last longer.

Controls

• Play, Step, Reset: Step advances one generation (every ant moves once). Reset clears the grid and puts the ants back at the start.
• Speed: from 1 step per frame up to 30,000 steps per frame.
• Paint, Add ant, Pan: with Paint, click or drag on the grid to set cells to the chosen colour. With Add ant, a click puts a new ant on that cell, facing up (at most 64). With Pan, drag to move the view. Shift-drag, right-drag or two fingers pan in any tool.
• Zoom: mouse wheel, pinch, or the + and − buttons. Fit grid shows everything; Fit pattern zooms to the coloured area.
• Keyboard (grid focused): Space plays or pauses, period steps, R resets, arrow keys pan, + and − zoom, 0 fits the grid.
• Rule string: type your own rule and press Apply, or pick a preset.

How it works

Chris Langton introduced the ant in 1986. In the original version the cells are white or black. On a white cell the ant turns 90 degrees right, turns the cell black and steps forward. On a black cell it turns 90 degrees left, turns the cell white and steps forward. Written as a rule string this is RL: the first letter says what to do on the first colour, the second on the second colour.

Extra colours work the same way. The rule is a string of letters, one per colour. Standing on colour k, the ant turns as letter k says, changes the cell to colour k+1 (the last colour wraps back to the first) and moves one step. L and R are the classic turns; this page also accepts N (no turn) and U (U-turn). Ants with more colours have been studied in depth and are often called turmites.

The highway is the surprising part. After about 10,000 steps the classic ant falls into a cycle of 104 steps that moves it two cells diagonally and leaves the same band of coloured cells behind, over and over. The page spots it by comparing the ant’s position every 104 steps and reports a highway after five identical shifts, so its estimate of the start is only roughly right.

Nothing in the two rules mentions a highway, so it is a good example of emergence. Two results are proven: the ant’s path never stays inside a finite region (Bunimovich and Troubetzkoy, 1992), and predicting its far future is computationally hard (Gajardo, Moreira and Goles, 2002). Whether every finite starting pattern eventually leads to a highway is still an open question. Every pattern tried so far has, but nobody has a proof.

Rule strings with a mirror-like structure, such as LLRR and RLLR, are known for patterns that become mirror-symmetric across a diagonal again and again as they grow (the page does not draw the symmetry line, so look for it at low speed). Other rules grow irregular blobs or large filled regions with straight diagonal edges.

Things to try

• Run the classic ant at 100 or 300 steps per frame, then switch on Follow the first ant and watch the highway. On the smallest grid it soon wraps around and crashes into its own trail.
• Pause during the early chaos, paint a wall of cells across the future path of the highway, and run again. Does the ant find another way?
• Apply LLRR and look for the mirror symmetry. Then try RLR and LRRRRRLLR and compare the shapes they grow.
• Use the Two ants preset, or the Add ant tool, and watch how the ants disturb each other’s paths.
• Type your own string, for example RRLL, RLN or LRU, and see what turns up.

Frequently asked questions

Is the ant random?

No. Every step is fixed by the rules and the grid. It only looks random during the chaotic phase because the pattern is too tangled to predict by eye.

Why does the highway appear after about 10,000 steps?

Nobody has a simple explanation. The number comes from simulation; no short argument predicts it.

Why does a small grid behave differently?

The grid is a finite wrap-around surface, not an infinite plane. Once the highway meets its own history, the result no longer matches the infinite case.

What does the PNG contain?

The whole grid, enlarged to about 1,024 pixels on a side, with ants as dots, always in light colours.

Sources

• Langton CG (1986). Studying artificial life with cellular automata. Physica D 22(1–3), 120–149. The paper in which the ant was introduced in 1986.
• Bunimovich LA, Troubetzkoy SE (1992). Recurrence properties of Lorentz lattice gas cellular automata. Journal of Statistical Physics 67(1–2), 289–302. The proof that the ant’s path never stays inside a finite region.
• Gajardo A, Moreira A, Goles E (2002). Complexity of Langton’s ant. Discrete Applied Mathematics 117(1–3), 41–50. Predicting the ant is computationally hard, the roughly 10,000 chaotic steps before the highway, and the open question for finite starting patterns.