Langton’s Ant

About this piece

One ant starts on an empty grid of 176 by 110 squares whose edges are joined, so walking off the right edge brings it back on the left and walking off the bottom brings it back at the top. It takes 250 steps a second. Every square it has turned dark is drawn in the theme’s cobalt ink, the path of its last 200 steps glows coral, and the counter in the corner gives the step number. For the first forty seconds the picture is a growing, ragged blob with no visible order. Then a straight ribbon sets off diagonally from its lower-left edge, and the counter adds the step the highway began on as soon as the ant has repeated its cycle three times. The camera starts close in on the ant and pulls back as the drawing grows, until the whole grid is on screen. After 16,000 steps the run holds for four seconds, fades, and the grid is cleared. Every other run is not the ant but one of two many-coloured turmites, described below. With reduced motion switched on you get one still: the ant’s finished run, the blob and the highway it built.

The rule

Chris Langton described the ant in 1986. In the words of the Wikipedia article on Langton’s ant (read 9 October 2026):

at a white square: turn 90° clockwise,
                   flip the colour of the square,
                   move forward one unit
at a black square: turn 90° counter-clockwise,
                   flip the colour of the square,
                   move forward one unit

That is the whole program. The order matters: the ant flips the square it is leaving, then moves. A worked start, with the ant facing up on an all-white grid: it turns right, blackens its square and steps right; turns right, blackens, steps down; again, steps left; again, steps up, and is back on the square it started on, facing up, with a 2 × 2 block of black squares behind it. Its fifth step is the first one on a black square, so it is the first left turn, and the symmetry starts to break. The test suite plants the opposite order (move first, then flip the square it lands on) and requires the highway checks to fail on it, which they do: that is a different machine.

Ten thousand steps of mess, then a highway

The Wikipedia article describes three phases: simple, often symmetric patterns for the first few hundred steps, then a pseudo-random tangle “until around 10,000 steps”, then a recurrent “highway” of 104 steps that repeats indefinitely. Wolfram MathWorld’s entry on Langton’s ant (read 9 October 2026) gives the size of each repeat: the 104 steps repeat indefinitely, “each time displacing the ant two pixels vertically and horizontally”.

Measured on this plate’s own code, counting from an empty grid: from step 9,976 onward, every stretch of 104 steps moves the ant exactly two squares left and two squares down, with no exception up to the end of the run. At that moment the tangle holds 716 black squares in a box 49 squares wide and 45 tall. Each 104-step cycle then adds exactly 12 black squares to the road, which is why it grows at a steady rate while the blob stops changing. A run lasts 16,000 steps, so the highway gets 58 cycles, about 24 seconds, and its 116-square diagonal wraps once through the bottom edge of the grid. The test suite checks the cycle on the plate itself: after step 9,976 the 104-step displacement is the same for more than 20 cycles in a row, and no run of 20 equal 104-step displacements starts anywhere before step 9,000.

Why it can never stay in a box

Every step the ant turns 90°, so its moves alternate strictly between horizontal and vertical. Building on that, it can be proved that the ant’s path is unbounded: whatever finite pattern of black squares it starts on, it never stays inside any fixed box forever. Wikipedia notes that this result is known as the Cohen–Kong theorem even though the attribution is incorrect; MathWorld spells it Cohen–Kung. What has not been proved is that the ant always ends up on a highway. MathWorld says only that this is believed, “although it might in principle take an extremely long time”. So the highway you watch here is a fact about this particular start, an empty grid, checked by running it, not a theorem. The ant is also more powerful than it looks: according to Wikipedia, in 2000 Gajardo and colleagues showed how a single ant’s trajectory can compute any Boolean circuit.

The two turmites

Greg Turk and Jim Propp extended the ant to more than two colours, as the Wikipedia article explains. The colours advance in a cycle, and the rule is named by one letter per colour, L or R, for the way the ant turns on that colour. Langton’s ant is RL. They belong to the family the Wikipedia article on turmites defines as Turing machines with an orientation, running on a two-dimensional grid of cells; A. K. Dewdney named them “tur-mites” in Scientific American in 1989, after Greg Turk wrote to him about them. Their colours here run from the cobalt ink to the coral one, and 0 is the empty square.

• LLRR, 300,000 steps at 5,000 a second. The article’s caption: it “grows symmetrically”. It also gives a sufficient condition: a rule name that, read as a cycle, is made of pairs of identical letters (LL or RR) produces symmetric patterns. Measured on this plate: in 300,000 steps the ant comes back to its starting square many times, and on 6,134 of those visits the whole grid is an exact mirror image of itself across a horizontal line just below that square. The last of them is at step 300,000, so it is still happening when the run stops. The test suite checks this on the plate’s own step function.
• LRRRRRLLR, 60,000 steps at 1,100 a second. The caption: it “fills space in a square around itself”. Measured: after 60,000 steps the squares it has visited form a box of exactly 100 × 100, and 97.7% of that box is coloured. The colour that fills most of the square is drawn faintly so that the structure inside it shows. The test suite checks both the square shape and the fill.

How it is computed

Each run has its own rate in steps per second, and the number of steps taken is the run’s age in wall-clock seconds times that rate, rounded down. The frame rate only decides how many steps fall between two pictures, never which steps are taken. The test suite runs 10,000 steps at 30 and at 144 frames per second and requires the two grids to be identical, square for square. The ant starts near the top-right corner, facing up, so the highway runs down and to the left through empty grid. On this torus it stays intact until step 16,794, past the end of the run. The grid is drawn one pixel per square into a small off-screen canvas and scaled up without smoothing. The camera frames everything visited so far with a margin and never shows fewer than 40 squares across. It is computed from the grid alone, so it cannot change what the ant does.

The two plates it sits nearest

• Game of Life is also a grid of squares with a tiny rule, but there every square updates at once from its eight neighbours, and patterns arise everywhere at the same time. Here only one square changes per step, the one the ant is standing on, so everything is drawn by a single moving point. That is why the ant’s picture is a path you can follow, and why its order arrives all at once, as one road, instead of as many small objects.
• Rule Thirty Cascade is a one-dimensional automaton whose rows are drawn one under another, and it never settles into a repeat. The ant goes the other way: chaos first, then a perfectly periodic structure that lasts forever. Side by side, the two show that a simple rule can produce order out of noise or noise out of order.

Honest limits

The grid is finite. The edges are joined, so if the run went on, the highway would eventually run into the blob or into itself. On this grid that happens at step 16,794, and what the ant does afterwards is no longer Langton’s ant on an endless plane. The run stops at 16,000 for that reason.

The counter reports the highway after the fact. The highway is only recognisable once it has repeated. The counter waits for three identical cycles (312 steps) before it names the step the highway began on. It never guesses ahead.

One start, one heading. Start the ant facing another way, or on a grid that is not empty, and the highway can take a different number of steps to appear, head in a different direction, or, as far as anyone has proved, not appear at all. This plate shows only the classic empty-grid start.

Two turmites out of a great many. Every string of L and R letters is a turmite, and most of them do neither of the tidy things shown here. These two were chosen because a published caption says what they do and a test can check it.

Curious how the loop and canvas fit together? Read how it works →