Langton's Ant Simulator

Take a sheet of squared paper, every square white, and set an ant on one of them. Give it two instructions. On a white square, turn right, paint the square black and step forward. On a black square, turn left, paint it white and step forward.

That is the whole of Langton’s ant. Nothing in it is random and nothing is hidden. Each move follows from the color under the ant, and still, for about ten thousand moves, nobody watching can say what it will do next. Then, with no change in the rules, it starts to build a road.

A graduate student’s toy

Christopher Langton published the ant in 1986, in a paper called “Studying artificial life with cellular automata” in the journal Physica D. He had made it as a graduate student at the University of Michigan, alongside the loops that also carry his name. A year later he organized the first workshop on artificial life at Los Alamos, and he is counted among the founders of that field.

The ant is easier to describe than to classify. One reading makes it a Turing machine in two dimensions: the grid is the tape, the ant is the head, and the head has a heading. Another makes it a cellular automaton in which a single square carries the ant’s direction as extra colors. Either way it is a universe with one inhabitant and one law.

A warning about handedness, because the sources differ. The usual statement has the ant turn clockwise on white. Gale, Propp, Sutherland and Troubetzkoy, whose paper is the main source for the many-colored ants below, start from squares that turn the ant left. Their pictures are mirror images of everyone else’s. No count, period or symmetry changes, only which way the road points.

Three acts

From a blank grid the ant’s career falls into three parts. During the first few hundred moves it draws small, tidy patterns, and several of them are symmetric. Gale and his coauthors list three moments, times 184, 368 and 472, at which the squares the ant has visited form a figure that looks the same after a half turn. They add that these symmetries eventually stop, and that the whole episode still awaited a satisfying explanation when they wrote in 1995.

Then comes disorder. An irregular blot of black and white grows around the starting square while the ant wanders through it on a path that looks random and is not.

At around 10,000 steps the wandering ends. The ant falls into a cycle of 104 steps that it repeats without limit, and each repeat leaves it two squares along a diagonal from where the last one began. The trail it lays is the highway. The integer sequence tables record the change exactly: for an ant that starts facing west, every 104 moves add 2 to its x coordinate and take 2 from its y coordinate, and they add 12 black squares to the grid. The colors the ant reads begin repeating at the 9977th step.

All of this can be checked by hand, or rather by machine. Open the simulator on the classic ant and jump to step 11,000: the count reads 834 black squares, the figure in the sequence table. Run 104 more steps and it reads 846, with the ant 2 squares east and 2 south. Run 104 again: 858. The detector on the page compares what the ant reads step by step and reports that the repeat began at step 9,977. It also finds that the last half-turn symmetric pattern occurs at step 473, one step after the 472 the paper names.

What is proved and what is only seen

One fact about the ant is a theorem. Leonid Bunimovich and Serge Troubetzkoy proved in 1992 that the ant’s track is unbounded: whatever pattern of black and white it starts on, it cannot stay inside any finite region for ever. Gale and his coauthors call this the Fundamental Theorem of Myrmecology, and they note that an earlier account had credited it to the wrong people.

The highway is not a theorem. Every finite starting pattern anyone has tried ends on the same 104-step road, which suggests the road is where the ant always ends. Nobody has proved it. Gajardo, Moreira and Goles state it as a conjecture: from any start in which only finitely many squares differ from the rest, the ant eventually builds the periodic highway in some unobstructed direction.

The distance between those two statements is large. Unbounded means only that the ant leaves every box. It does not say when, or by what route, or that the departure is orderly. The same authors remark that there are very few results of any kind about how the ant moves.

They also show why results are scarce. With a suitable arrangement of squares, the path of a single ant can evaluate any boolean circuit, and from there it can imitate a universal Turing machine. Some questions about the ant on arbitrary grids are therefore undecidable: no procedure answers them in every case. The conjecture, if true, would rescue the finite starts. One would run the ant until the highway appeared and read the future off the repetition.

This is the limit of any simulator, this one included. It can run a start for millions of steps, find a repeat, measure its length and say when it began. It cannot show that the repeat lasts for ever, and it cannot say anything about the starts it has not run. So the page labels a highway as detected in one run up to its current step. It also has to stop somewhere: the plane is stored in 8,192 tiles of 64 by 64 squares, and the classic ant uses the last of them at step 13,637,229.

More colors, more ants

Greg Turk and Jim Propp gave the ant more colors. A square now cycles through a list of them, one step along at each visit, and the ant carries a string of letters, one per color, saying which way to turn on each. Langton’s ant is RL in this scheme. Longer strings are new animals.

Some of them are wild. RLR grows a shapeless blot, and it is not known whether it ever makes a highway. Some are tidy in ways the classic ant never is. LRRRRRLLR fills a square around its start, and RRLLLRLLLRRR builds a solid triangle that keeps growing. LLRRRLRLRLLR makes a highway of its own, far more tangled than the classic one; on this page its cycle measures 1,968 steps.

The strangest are the symmetric ones. Propp noticed that the four-color ants LRRL and LLRR keep coming back to their starting square with the whole pattern mirror symmetric, and that the six-color strings with the same habit all had code numbers divisible by three. That turned out to be no accident. Read as a ring, each such string is made of runs of L and runs of R of even length, and for those strings the return to symmetry can be proved.

The proof replaces each square with a tile carrying two quarter circles, an idea credited to Bernd Rümmler, so that the ant’s possible routes become closed curves. It then leans on the Jordan curve theorem. For LLRR the first four symmetric returns come at steps 4, 8, 28 and 32, and the pattern is symmetric again at step 16,464. Unlike the highway, this regularity is guaranteed.

Give the ant an internal state as well as a heading and it becomes a turmite, a name A. K. Dewdney coined in 1989 for machines Greg Turk had been studying. Allen Brady had reached the same idea a year earlier and called them turning machines. Their turns are left, right, none and about-face, and as a class they are as powerful as ordinary Turing machines. The simulator here keeps to one-state ants, with all four turns.

Two ants raise a question one ant never meets: what happens when they share a square? The answer has to be chosen, and the outcome depends on the choice. One sequence table follows two classic ants that start side by side with an empty square between them and move at the same instant. They meet seven times, the shared square is flipped once and not twice, and in the end both build highways.

What the ant is for

The ant is the cheapest demonstration there is that knowing the rule is not the same as knowing the outcome. The rule fits in two lines. The tables of where the ant stands after each move were made by running it, and nothing in the sources offers a formula for the disordered stretch.

It also shows how thin the line is between what is observed and what is known. The highway has been seen by everyone who has ever run the program. It is still a conjecture.

So the honest summary has three parts of unequal weight. The ant must leave: proved. Certain many-colored ants must return to symmetry: proved. The classic ant always ends on its road: seen every time, explained never. Forty years on, the smallest of Langton’s inventions is still ahead of the people watching it.