The Ant That Builds a Road

Place an ant on an all-white grid, facing one of the four compass directions. It reads the square underneath it and turns 90 degrees right on white or 90 degrees left on black. It then flips that square's colour and moves forward one square. Turning, flipping and moving together count as one step.

For example, an ant facing north on white turns east, colours its old square black and moves one square east. Its next turn depends on the colour of the new square, not the square it just left. The grid records the history; there is no random choice or destination built into the rule.

From the blank start, this laboratory detects a repeated 104-step path beginning at step 9,976 under the stated detection criterion. Each repeat ends two squares west and two squares south of where it began, creating a diagonal band called a highway.

The original mathematical setting is an infinite grid. This laboratory uses a finite grid with wrapping edges, so a long run can eventually meet its earlier path. The finite highway detector checks a stated number of repeats; it does not prove endless continuation or a highway for every possible starting pattern.

Two observations do most of the work, and neither of them explains the road.

The ant reads what it wrote. Every square it leaves has changed, so the grid is a message the ant is writing to itself. That is why a rule with no memory can behave as though it has one, and it is also why nothing about the ant can be predicted by looking only at the rule. The interesting object is not the ant. It is the ant together with the grid it has already coloured.

Nothing can ever be undone by accident. Take the ant at any moment and ask where it just came from. It stepped forward in the direction it is now facing, so it came from the square immediately behind it. That square was flipped on the way out, so flipping it back recovers what the ant actually read, and what it read is precisely what decided the turn. Undo the turn and you have the heading it arrived with. Every state has exactly one predecessor, computed rather than searched for.

The consequence is worth pausing on, and it is smaller than it first looks. A machine that can always be run backwards can never fall into a loop, because falling in would need two different states leading into the same one. So the ant cannot wander for a while and then settle into a cycle.

It can, however, be in a cycle from its very first step, and reversibility says nothing against that. Set the turn word to LL and watch: the ant walks a two-by-two square, uncolours everything it coloured, and after eight steps it is on the square it started on, facing the way it started, with an empty grid in front of it. Then it does the same eight steps again, forever. That run is reversible like every other, and it never leaves a patch four squares across. So a turn word can be periodic, and the statement that the ant must travel arbitrarily far is a theorem about RL rather than about ants in general.

For RL the loop is ruled out too, by a published argument about the boundary of the region the ant has visited. This page cites that argument and does not reproduce it, which is worth saying plainly, because the reversibility above is the part you can check yourself and it is not the part that does the work.

Either way it is a long way from explaining the road. It says the RL ant will not stop; it says nothing about why it starts building something so regular that a person can measure its period.

The sentence worth carrying away is this one.

The step at which the road begins is not a fact about the rule. It is a fact about the rule, the starting grid, and a definition of "road" that somebody had to choose.

All three parts of that are load-bearing, and the laboratory lets you test each one.

Change the starting grid and the number moves. Colour four squares around the ant before it starts, which the control panel will do for you, and the road appears at step 542 rather than step 9,976. The rule did not change; the message the ant reads first did.

Change what counts as a road and the number moves again. This page uses a criterion it states in full: the road begins at the first step from which the trajectory is exactly itself, translated, over eight consecutive stretches of 104 steps. Demand fewer stretches and you would accept flimsier evidence; demand more and you would push the number later. As it happens the number is the same at two, four, eight, sixteen and twenty-four stretches for this run, which is checked in the test suite, and that stability is a small piece of evidence that the criterion is measuring something real rather than being tuned to a nice answer.

What does not change is the shape of what happens. Every finite starting configuration anybody has run has eventually produced a road. Nobody has proved that one has to.

Let the grid be ${\mathbb{Z}}^2$, with a colouring $c:{\mathbb{Z}}^2\to \{0,1,\dots ,k-1\}$ in which all but finitely many squares hold $0$. A turn word is a string $w\in \{L,R{\}}^k$. The ant's state is $(p,d,c)$ with $p\in {\mathbb{Z}}^2$ and $d$ one of four headings, and one step is

Write $p(t)$ for the position before step $t$, and for a period $P$ define $D(t)=p(t+P)-p(t)$.

1. Each step has a unique predecessor, so the map on states is injective. Proved, and reproduced here.
2. For $w=RL$ and any starting colouring with finitely many coloured squares, the trajectory $\{p(t)\}$ is unbounded. Proved in the literature, cited rather than reproduced.
3. From the empty grid with $w=RL$, the smallest $s$ with $D(s)\ne 0$ and $D(t)=D(s)$ for all $t\in [s,s+832]$ is $s=9,976$, with $D(s)=(-2,+2)$ and $P=104$. Observed, in exactly one run of the computation described in the ledger.
4. Whether every finite starting colouring with $w=RL$ eventually admits such an $s$ is open.
5. For $k=2$, the number of coloured squares changes by exactly $1$ at every step. Proved.

Statement 3 is the one the page is arranged around, and it is the weakest of the five: it is a measurement, and its scope is one run.

Every step is reversible. Given the state after a step, let $d^{\prime }$ be the current heading and $p^{\prime }$ the current position. The step moved the ant forward along $d^{\prime }$, so $p=p^{\prime }-d^{\prime }$. The step also advanced the colour of $p$, so $c(p)=c^{\prime }(p)-1\mathrm{mod}k$ recovers the colour that was read. That colour selects the letter $w_{c(p)}$ of the turn word, and $d={\mathrm{turn}}^{-1}(d^{\prime },w_{c(p)})$ recovers the heading. Every quantity on the right is available and the result is unique, so the map on states is injective. ∎

Therefore the ant never repeats a state, once the published theorem is granted. Suppose $S_i=S_j$ for $i<j$. Applying the inverse $i$ times gives $S_0=S_{j-i}$, so the trajectory is periodic with period $j-i$ from the start, and in particular it visits finitely many states. But each of the first $j-i$ steps moved the ant to an adjacent square and the colouring is determined by the states, so periodicity in the state forces periodicity in the position, and the ant would be confined to a bounded region. The published theorem rules that out for the plane. Here, the point that stands on its own is the injectivity: no finite computation is being trusted, and no step limit is being mistaken for an answer. ∎

The count of coloured squares moves by one, for a two-letter word. One step touches exactly one square and changes its colour from $0$ to $1$ or from $1$ to $0$. Both cases change the number of non-zero squares by exactly one, in opposite directions. Hence the graph in the "coloured squares" view is made of unit steps, and any straight stretch of it means the ant is adding the same number of squares per period, which is what a repeating sequence of moves does. ∎

What is not proved here. The road. Not that it begins at step 9,976, which is a measurement of one run; not that it begins at all, which is the open question; and not that it continues forever once begun, which this page checks only as far as it runs. The straight-line extrapolation drawn on the counts view stops where the computation stops, deliberately.

What this laboratory computes. Up to 50,000 steps of one ant on a square torus, at most 2,001 squares on a side, in exact integer arithmetic with no floating point anywhere in the rule. The torus is a compromise the mathematics does not make: leaving the right edge arrives at the left, so a run that reached the edge would be a picture of a different machine. Every run therefore records whether it got near the edge, and the widths are chosen, and re-measured in the test suite, so that none of the runs offered here does.

A run of fifty thousand steps that finds nothing has found nothing. The turn word LRRRRRLLR stays within 43 squares of its start for the whole run and the detector reports no road at any period it examines. That is not evidence that it never builds one. By the cited theorem it is going to leave any region you draw around it eventually, and this page simply stops watching first. The ledger marks that result observed for exactly this reason.

Where the mathematics is still moving. The open question is whether every finite starting configuration eventually produces a road. It has resisted since the ant was first studied, and one reason to expect it to keep resisting is that the ant is powerful enough to simulate an arbitrary computation given a suitable starting grid: a short general argument about what it always does would be a short general argument about what every computation does. Related questions with rather more progress behind them concern turn words longer than two letters, where some words provably fill the plane with a symmetric pattern and others are as opaque as RL.

Read this next to the Collatz orbit atlas. The two pages are the same predicament in different clothing: a rule small enough to write on a hand, a pattern that every computation anybody has run agrees on, and a general statement that no amount of computation touches. Reading them together makes the distinction this whole site is built around concrete, because in both cases the evidence is overwhelming and the question is open, and those two facts are not in tension.