A little noise gets Langton's ant to its highway up to five times sooner
On an empty grid, Langton's ant wanders chaotically for 9,977 steps and then starts building its "highway", a pattern that repeats every 104 steps and carries it off diagonally forever. When I started it inside a small random patch (8×8 cells, any density), the median wait fell to about 2,000 to 4,000 steps. Big patches are the opposite: in a 512×512 patch the ant needed a median of 155,000 steps at 30% density and 1.3 million at 5%. The highway never formed deep inside the noise. Every one started near the patch's edge.
The rules
The ant sits on a grid of white and black cells. On a white cell it turns right, on a black cell it turns left. Either way it flips the cell's color and steps forward. Starting from all white, it makes symmetric-looking shapes for a few hundred steps, then a mess, then at step 9,977 the highway. Nobody has proved it always gets there, though in every experiment so far it has.
Try it. Pick a patch size and a density, and the ant starts on a fresh random patch. "Highway forming" means the turns have started repeating; the onset only counts once the ant has left everything it touched before.
The test
I put a k×k patch of random black cells (each black with probability p) around the ant's start, then ran it until the highway was permanent. "Permanent" means the ant's turns repeated with period 104 for at least 12 periods and the ant then left the box containing every cell it had touched before, plus the patch. Outside that box the grid is blank, so nothing can interrupt the highway after that. The onset is the first step of the periodic stretch. I ran 400 random patches per cell of the table, all 400 found a highway, and the empty-grid case reproduced 9,977 exactly.
Median steps until the highway starts:
| patch | p = 0.05 | 0.1 | 0.2 | 0.3 | 0.5 | 0.7 | 0.9 |
|---|---|---|---|---|---|---|---|
| 4×4 | 9,977 | 2,802 | 1,994 | 1,959 | 1,906 | 2,194 | 1,500 |
| 8×8 | 2,098 | 1,997 | 2,337 | 2,585 | 2,902 | 2,886 | 3,967 |
| 16×16 | 3,555 | 3,429 | 3,825 | 3,363 | 4,164 | 5,400 | 5,468 |
| 32×32 | 7,046 | 7,493 | 5,976 | 7,151 | 8,554 | 8,757 | 10,534 |
| 64×64 | 19,302 | 14,875 | 13,387 | 14,184 | 15,545 | 17,343 | 22,432 |
| 128×128 | 57,328 | 42,314 | 29,878 | 25,668 | 31,854 | 37,198 | 50,785 |
| 256×256 | 244,260 | 123,163 | 70,723 | 65,305 | 74,783 | 88,075 | 134,161 |
(The 4×4 patch at p = 0.05 is empty 44% of the time, which is why its median is exactly the empty-grid number.)
Small noise is a shortcut
With a 4×4 or 8×8 patch, 80% to 95% of runs beat the empty grid's 9,977 steps. The empty start is just one particular initial condition, and a slow one. A few random black cells move the ant onto a different chaotic path, and most of those paths find the highway sooner. The spread is wide, though: the slowest small-patch runs took 30,000 to 100,000 steps.
Big noise has to be escaped
Random cells in the highway's path tend to wreck it, so the ant has to get to the edge of the patch first. When my check confirmed a highway, the ant was always outside the patch. Taking off the 24 cells the highway travels during the 12-period check, the median start for large patches was within about a dozen cells of the edge, on one side or the other. So for big patches the wait is the time it takes to get out, and that depends a lot on density. I added a 512×512 patch for three densities:
| patch | p = 0.05 | p = 0.3 | p = 0.9 |
|---|---|---|---|
| 64×64 | 19,675 | 14,344 | 22,655 |
| 128×128 | 62,333 | 28,609 | 52,896 |
| 256×256 | 253,355 | 67,440 | 136,189 |
| 512×512 | 1,310,979 | 154,709 | 456,235 |
At 30% density, doubling the patch side roughly doubles the wait, so the time is close to proportional to the distance to the edge. At 5% each doubling multiplies the wait by more and more (3.2x, then 4.1x, then 5.2x), so it's growing faster than the patch's area. In the 512 patch that's 0.6 steps per patch cell at 30% and 5 steps per cell at 5%. Dense noise (90%) sits in between. Sparse noise is the hardest kind to leave. I checked whether that is because the ant wanders more of a sparse patch, by counting the patch cells it had visited when the highway began (40 runs at 512, 400 at the smaller sizes). In the 512 patch the ant visited 31% of the cells at 5% density against 18% at 30%, so sparse noise does make it cover more ground. In 16 to 64 patches the two densities were the same (64: 56% at both), so the effect only shows in large patches. In the small ones the ant sweeps most of the patch (93% at 16, 56% at 64) before leaving.
So what
The famous 9,977 isn't a typical number. It's one sample, and a slow one for small disturbances. For a large random start, there's a best density, near 0.3 here, where the ant escapes fastest. Sparse starts are the slowest by far.
Method: a 40-line Node script on an 8192×8192 grid, 400 patches per setting across 10 cores (about 15 seconds of compute for the whole table). Only square patches centred on the ant. I didn't look at other ant rules or other patch shapes.