About Langton's Ant
An ant walks on a floor of tiles. On a light tile it turns right, on a dark tile it turns left; either way the tile it is standing on changes colour, and it steps forward one tile. That's all. Press RUN to watch it (pick a speed first), STEP to move one step at a time, or type a number into Go to step. Drag the floor to look around, use the wheel (or pinch) to zoom, and FIT to see everything again. Keys: Space runs or pauses, N takes one step, F fits.
The rule letters say what the ant does on each colour of tile, one letter per colour: R turn right, L turn left, N no turn, U turn round. Each time the ant leaves a tile, that tile moves on to the next colour in the list, and the last colour goes back to the first. The classic ant is RL. Click a coloured tile under the rule to change its letter. You can also start with up to four ants, or on a scattered floor of random tiles. COPY LINK copies a link to exactly what's on the floor.
THE STORY
Chris Langton, one of the founders of the study of artificial life, described the ant in 1986. It is a favourite example of how very simple rules can do something nobody can predict from the rules alone. Started on a plain floor, the ant makes small, almost symmetric patterns for the first few hundred steps, then a growing, messy blob for about ten thousand. Then, out of the mess, it starts building a highway: the same 104 steps over and over, each lot moving it two tiles diagonally, for ever. Here the highway begins at step 9,977.
What has been proved is that the ant can never stay inside a limited area: from any starting floor with finitely many dark tiles, it eventually wanders off without bound (Leonid Bunimovich and Serge Troubetzkoy, early 1990s). That it always wanders off by building the highway is only a conjecture. Every finite starting floor anyone has tried ends in the highway, but nobody has proved that it must. Try a scattered floor and see. In 2002 Anahí Gajardo, Andrés Moreira and Eric Goles showed that, given the right starting floor, the ant's path can work out any logic circuit, so in principle it can compute anything a computer can.
Ants with more colours came soon after. Greg Turk and Jim Propp looked at rules written as strings of L and R, and A. K. Dewdney's Scientific American column made these creatures (and their relatives with an inner memory, called turmites, from Turing machine and termite) widely known around 1989. Their behaviour varies wildly: RLR grows a chaotic blob for as long as anyone has run it, LRRRRRLLR fills a square, RRLLLRLLLRRR builds a filled triangle that travels. Rules whose letters come in pairs (LLRR, or RLLR read round in a ring) keep coming back to a perfect mirror image, which David Gale, Jim Propp and colleagues proved in the 1990s. In this app's Mirror pattern it happens each time the ant is back on its first tile, facing up as it started.
HOW IT WORKS
The floor is endless, so it is kept in sections of 64 × 64 tiles that are only made where an ant has been; each tile is a single byte. Each step is a few lines of arithmetic, so the fastest setting manages millions of steps a second, and only the sections that changed are redrawn; zoomed far out, each block of tiles is drawn in its strongest colour so thin trails stay visible. With 6,000 sections (about 24 million tiles) laid, the floor is full and the run stops: the classic ant gets there after nearly ten million steps, about 190,000 tiles along its highway.
The highway is spotted by watching the ant's own moves (which way it went, and the colour it stood on). If its last moves have repeated with some period at least four times over, and for at least 600 steps, the app says so, with how far the ant drifts each time round; the start of the highway is how far back the repeats go. If it drifts nowhere, the ants are stuck in a loop (as the Dancing pair are). When a run stops, a small floor is also checked for a mirror image.
FURTHER WATCHING AND READING