Ant — 9x

What you are looking at

An ant stands on a square of an infinite grid. Every square is white to begin with. The ant obeys two rules and nothing else:

On a white square: turn 90° right, flip the square to black, step forward one.
On a black square: turn 90° left, flip the square to white, step forward one.

That is the whole program. It fits in a sentence, it has no memory beyond the grid itself, and it is completely deterministic — run it twice and you get the same picture twice.

For the first few hundred steps the ant makes small symmetrical figures, little rosettes, and you would guess it was going to stay tidy. It does not. Around step 500 the symmetry breaks and the ant spends the next ten thousand steps producing something that looks, by every test anyone has applied to it, like noise. A shapeless black blob. No pattern, no drift, no obvious structure.

Then, at roughly step 10,000, it stops. Without warning and without any change in the rules, the ant locks into a cycle of 104 steps that displaces it two squares diagonally, and it repeats that cycle forever, building a straight highway out to infinity. Nobody has explained why. The transition is not caused by anything in the grid you can point to; it simply emerges, and it emerges from almost every starting configuration anyone has tried.

The one thing that has been proved is oddly weak, and it is called the Cohen–Kong theorem: the ant's trajectory is unbounded. It always escapes to infinity, no matter what finite pattern of black squares you start it on. That the escape always takes the form of the same 104-step highway is, as of today, an observation and not a theorem.

The world on this page is finite and wraps at the edges, so a highway left running long enough eventually comes back in the far side and drives through its own wreckage. Everything worth watching happens well before that.

Try this

Run the classic rule RL at Normal speed and watch the Highway readout. It says "not yet" for about ten thousand steps and then names the period it found. The machine is not told to look for 104; it searches for any repeating displacement, and 104 is what turns up.
Switch to RRLL. This one never goes chaotic; it grows a filigreed, bilaterally symmetric shape that keeps its symmetry forever.
Try LRRRRRLLR, a nine-state rule. Long rules tend to fill space rather than build roads, and they do it in colours.
Turn Starting noise up to 10% and press New noise. The ant still finds a highway — usually a different one, at a different time, in a different direction. Sometimes it takes far longer.
Set the speed to Blur to skip the boring middle, then back to Single step to watch the ant actually lay a course of the road.

Notes

Chris Langton introduced the ant in 1986 as part of his work on artificial life at Los Alamos. It is a turmite — a Turing machine whose tape is a two-dimensional grid — and generalising it is as easy as adding colours. A rule string like RRLL means four colours: on colour 0 turn right, on 1 turn right, on 2 turn left, on 3 turn left, always advancing the colour by one. Everything on this page except the colour palette is that one loop.

Langton's ant with a suitable finite starting configuration is Turing complete, which puts a firm ceiling on what can be known about it. There is no general shortcut for predicting what it will do; the only way to find out is to run it. The ten thousand steps of noise are not a failure of analysis. They are, in a precise sense, the answer being computed.

What you are looking at

Try this

Notes

Further reading