The ash a random soup leaves

The essays here on cellular automata have stayed, mostly, on a line: the eight cases of an elementary rule, rule 110’s gliders and the computation they carry, rule 30’s centre column. The two that left the line, the sandpile and Langton’s ant, each followed one deterministic process to its end. This essay takes the most famous two-dimensional rule of all and asks a statistical question about it: what does it do to randomness?

John Conway’s Game of Life, published by Martin Gardner in Scientific American in October 1970, lives on the square grid. Every cell is alive or dead, and every cell has eight neighbours. At each step, all at once, a dead cell with exactly three live neighbours comes alive, a live cell with two or three live neighbours stays alive, and every other cell is dead in the next generation. Conway chose the numbers after trying many alternatives, looking for a rule under which patterns would neither die out quickly nor grow without bound, and that would be hard to predict. He found one that is, in a precise sense, impossible to predict.

Five cells and a thousand generations #

The R-pentomino is five cells in the shape of a lower-case r, and it was the first pattern Conway’s group could not follow by hand. The figure runs it exactly, on a grid large enough that nothing reaches the edge. It grows irregularly, splits, throws off its first glider — a five-cell object that reproduces itself one cell diagonally every four generations — at generation 69, peaks at 319 live cells around generation 821, and then slowly burns down. From generation 1,103 on nothing changes except blinkers flipping between their two states and six gliders flying away. The final population is 116, the gliders included.

The figure detects the end by the population: from generation 1,103 the count repeats with period two to the end of the run, and not from any earlier generation. Neither the number 1,103 nor the number 116 can be guessed from the five starting cells. That is the general character of Life, and it is not an accident of this pattern.

Three methuselahs #

Small patterns with long lives are called methuselahs, and the figure follows three. The R-pentomino settles at 116 after 1,103 generations. The acorn, seven cells found by Charles Corderman in 1971, takes 5,206 generations and settles at 633 cells, its population having passed a thousand on the way. The diehard, also seven cells, lives exactly 130 generations and then vanishes entirely — not a cell left. Three patterns of nearly the same size have lifetimes of 130, 1,103 and 5,206 generations and fates from nothing to six hundred cells.

The computation has to handle the gliders. They move away for ever, and a grid large enough to hold the acorn’s gliders at generation 5,206 would be thousands of cells across. Instead, cells that wander more than 380 cells from the centre are deleted and counted; a glider that far out has left the debris behind and can never return. The population curves count them as still alive.

Methuselahs are found by search rather than design. A program runs every pattern that fits in a small box, or millions of random small patterns, records how long each lives, and keeps the record holders; the acorn and the diehard were found by people running patterns by hand and by early computers, and later searches have found patterns of a dozen or so cells that live for tens of thousands of generations. What makes a long life is never visible in the seed. A methuselah is a pattern whose early growth happens to avoid the collisions that would stabilise it, and whether a given seed does that is decided only by following it — which is exactly the property the undecidability theorem below says cannot be shortcut. The records will go on being broken for as long as people search, because nothing bounds how long a small pattern can live except the size of the box and the patience of the search.

A soup burns down #

The statistical question starts from random soup: a grid on which each cell is alive or dead by a fair coin. To avoid edges, the grid is a torus — the right edge joined to the left, the top to the bottom — 96 cells each way. In the first generation most of the soup dies: a live cell needs two or three live neighbours, and with half the cells alive the average live cell has four. Survivors form a churning, irregular mass that spreads, collides with itself and thins. Within a few hundred generations most of the torus is empty, and what is left is ash: small, separate objects that either never change or repeat every two generations, with gliders occasionally crossing between them.

The figure’s soup starts with 4,627 live cells and ends, after 4,000 generations, with 365 — 4.0% of the torus. Across the soups in the next figure the average is 3.1%. The randomness at the start is almost entirely destroyed: a soup of 9,216 independent coin tosses becomes a few dozen small objects whose positions and kinds are all that remain of it.

The first generation, and the guess that fails #

The first step of the burning can be computed exactly. In a soup where each cell is alive with chance one half, a cell is alive in the next generation if it has exactly three live neighbours, or if it is alive and has exactly two. Its eight neighbours are independent coin tosses, so the chance is

$$\binom{8}{3}\frac{1}{2^8} + \frac12\binom{8}{2}\frac{1}{2^8} = \frac{56 + 14}{256} = 0.273,$$

and a soup at density one half drops to about 27% in a single generation. The same calculation with a general density $d$ gives a map $d \mapsto \binom83 d^3(1-d)^5 + \binom82 d^3 (1-d)^6$ that predicts the next density from the current one, as if every generation were a fresh soup. Iterated, as a cobweb would trace it, the map has an attracting fixed point at 0.370: the guess says that Life settles into a seething equilibrium with 37% of its cells alive.

The real soup reaches 3%, a twelfth of that. The guess fails because after the first generation the cells are no longer independent. Live cells cluster, clusters stabilise into blocks and blinkers, and a block is a configuration in which every cell’s fate is locked by its neighbours’ — the opposite of independence. This mean-field prediction, which treats each cell as surrounded by an average of its neighbours, is the first approximation for almost any lattice model, and in Life it is wrong by an order of magnitude, because the rule’s whole interest is in the correlations it builds.

What the ash is made of #

Sorting the ash needs a definition of a piece and a way to recognise it. A piece here is a connected group of live cells, neighbours counted diagonally as well as across, and its shape is compared with a list of named objects after all eight rotations and reflections of the square, so that a boat facing any direction is still a boat. Twelve soups leave 745 pieces. Blinkers — three cells in a row, flipping between horizontal and vertical — are 31.5% of them; blocks, the two-by-two square that never changes, 29.7%; beehives, six cells in a hexagon, 14.8%; then loaves, boats, ponds, tubs and ships, with a single glider and a single beacon. About one piece in twelve is something else: an object not on the list, or two objects close enough to count as one connected piece.

The commonest objects are the smallest ones that are stable, and that is not a coincidence. A random fragment settles into whatever it can reach, and small stable objects are reachable from many more fragments than large ones. Large-scale censuses, run since the 1990s by Achim Flammenkamp and later by thousands of computers in a distributed search, find the same ranking at the top over billions of soups and a long tail of objects found only once or a handful of times, some of them never seen in any other way.

The starting density hardly matters #

Change the coin. A soup with only 5% of its cells alive leaves 0.7% after 2,500 generations: isolated cells die at once, and only the rare clusters that happen to start close enough survive. At 80% the soup dies almost entirely in the first two generations from overcrowding, leaving 0.3%. But between 15% and 60% the amount of ash is nearly flat, between about 3% and 4%: the soup forgets how dense it started. Once the first generations have destroyed the starting pattern, what remains is a churning mass whose statistics are set by the rule, not by the start, and it burns down to the same kind of ash in the same proportion. The curve is ragged because each point averages only ten soups on a small torus, and a single long-lived glider collision can double one soup’s ash; the flatness, not the wiggles, is the finding.

That forgetting is the reason a statistical picture of Life is possible at all. A single pattern’s fate is undecidable, as the next section explains; the average fate of a random one is a stable, measurable quantity, much as a single molecule’s path is unpredictable while the pressure of a gas is not.

How long a soup takes to settle #

How long does the burning take? The figure runs 300 soups on a smaller torus, 32 cells each way, and records the generation from which every cell either stays still or repeats every two generations. Half have settled by generation 355 and nine in ten by 926. The tail is long: the slowest soup here ran to generation 2,194. On a torus the usual culprit is a glider that escapes the debris, circles the torus and crashes back into the ash, restarting a local fire; every such collision can postpone the end by hundreds of generations, and on a small torus there is nowhere for gliders to escape to.

The distribution on the logarithmic scale is roughly symmetric, which means the settling times are spread over a factor of ten or more between the fast and the slow — the same heavy-tailed behaviour that the three methuselahs show one pattern at a time.

Why three and two #

Conway’s numbers are not the only choice, and their neighbours show why he settled on them. A rule in which a dead cell is born with two live neighbours, rather than three, explodes: almost any small seed grows into an expanding chaos that fills the plane. A rule in which live cells never die fills the plane with slowly growing blobs. Birth on three and survival on two or three sits between them: random patterns neither explode nor vanish but burn down to ash, and in the burning they produce gliders, oscillators and, rarely, structures that grow.

The closest relative studied in its own right is HighLife, in which a dead cell is also born with six live neighbours. Its soups behave almost exactly like Life’s, and it has one famous addition, a small pattern that copies itself — a replicator — which Life itself is not known to produce from any small seed. The difference between the two rules is one extra birth condition that random soup rarely triggers, and it changes what the rule can build without changing what it does to randomness. That is the general lesson the soups teach: the statistics of ash are robust to small changes in the rule, while the catalogue of exotic objects is not.

Why the end cannot be predicted #

The R-pentomino’s 1,103 generations are not a puzzle someone failed to solve; they are a symptom of a theorem. Elwyn Berlekamp, John Conway and Richard Guy showed in 1982, in Winning Ways, that Life can simulate any computer. Gliders carry signals, glider guns — the first, found by Bill Gosper in 1970, emits a glider every thirty generations — produce streams of them, and collisions between streams implement logic gates and memory. A Life pattern can therefore run any program, and whether it eventually settles is as hard to decide as whether the program halts — which, as the halting problem showed, no algorithm can decide in general.

So there is no procedure that takes a starting pattern and returns the generation at which it settles, or whether it ever will. For any particular small pattern the answer can be found by running it, and the methuselah figure does exactly that; what cannot exist is a shortcut that works for every pattern. Rule 110 made the same point on a line. Life makes it on a plane, with a rule a child can follow and patterns a child can draw.

Gosper’s gun also answered the question Conway posed in Gardner’s column: whether any finite pattern grows without bound. Conway offered fifty dollars for an answer and believed it was no; the gun, emitting gliders for ever, made it yes. That a population can grow for ever and that whether it does is undecidable are two halves of the same richness.

What the simulations show and assume #

Every generation is computed exactly. Single patterns run on a finite grid large enough that nothing but escaping gliders goes far, and those are deleted at a fixed distance and counted, which is exact as long as a glider that far out can never interact with anything again — true here because the debris it left is hundreds of cells behind it and nothing else lies ahead. The soups run on tori, and a torus is not the infinite plane: gliders that would escape an infinite soup circle a torus and collide, which makes small tori settle later and leave slightly different ash. The census matches pieces against a short list, so a pair of objects close enough to touch diagonally is counted as one unnamed piece. The settling time is detected from the population, which repeats with period two once everything has settled; in principle a soup could reach a state with a longer period, and the detection would then report it as unsettled.

Still open: what a random soup can make #

The census raises questions the computation cannot settle. Which objects can arise from random soup at all, and with what frequency? Some patterns cannot arise from anything: Edward Moore and John Myhill’s Garden of Eden theorem of 1962–63 shows that Life has configurations with no predecessor, because it has distinct patterns that evolve into the same one, and explicit Gardens of Eden have been found, the smallest known fitting in a box of a few dozen cells. Between those and the blocks and blinkers of every soup lies a vast range of objects whose natural frequencies are unknown, and some that have never appeared in billions of soups may appear once in the next billion. Whether the ash density of an infinite random soup has a definite limit, and what it is, has been measured to a few digits and never derived; even that the infinite soup settles at all, with probability one, has not been proved.

A rule that forgets its start #

Conway’s rule turns a half-filled random grid into ash covering about three per cent of it — blinkers and blocks above all, then beehives, loaves and boats — and the amount barely depends on how full the grid started; the burning takes a few hundred generations, with a long tail of soups kept alive by wandering gliders. Single small patterns are less predictable than random ones: five cells settle after 1,103 generations, seven after 5,206, another seven die after 130. Because Life is a universal computer, no procedure can say in general when a pattern will settle — the statistics of random soup are measurable precisely because the fate of any one pattern is not.