Cellular Automata Simulator

The whole of rule 30 fits on an index card: eight tiny pictures of three cells and the cell that follows. You can learn it in a minute. Then you run it, and the card has told you nothing.

That gap is the subject. A cellular automaton is a lattice of sites, each holding one of a finite set of values, all updated at the same instant in discrete steps by one identical rule that looks only at a small neighborhood. John von Neumann arrived at the idea while working on machines that could build copies of themselves; it was Stanislaw Ulam who suggested a discrete system, and the automaton von Neumann designed lived on a two-dimensional grid. Each of its cells needed 29 states. The surprise of the decades since is how little is needed. Two states and a neighborhood of three cells are already too much to predict.

Eight bits make a rule

Take a row of cells, each black or white, and let each cell look at itself and its two neighbors. Three cells with two values each give 2 x 2 x 2 = 8 possible neighborhoods. A rule says, for each of the eight, what the middle cell becomes. Eight yes-or-no answers make an 8-bit number, so there are exactly 256 such rules, and the number is the rule. Write the neighborhoods in the order 111, 110, 101, 100, 011, 010, 001, 000 and read the answers off as binary digits. Rule 30 is 00011110: the cell turns black for 100, 011, 010 and 001, and white otherwise.

Here is that rule worked by hand. Start with one black cell in a white row. Only three cells have a black cell in view, and their neighborhoods are 001, 010 and 100, all of which give black, so the next row is 111. The row after that is 11001, then 1101111, then 110010001. Count the black cells in each row and you get 1, 3, 3, 6, 4. In the tool, choose rule 30, one cell and empty edges, press Reset and then Step four times: the live-cell counter reads 1, 3, 3, 6, 4, and a fifth step gives 9.

The 256 are not all different. Mirror a rule, or swap black and white, and its pictures are mirrored or swapped too. Counted that way, 88 fundamentally inequivalent rules remain. Rule 30 is the mirror image of rule 86.

Why one table draws noise and the next draws lace

Rule 90 has a table that can be said in five words: left neighbor exclusive-or right neighbor. From one black cell it draws a nest of triangles inside triangles, the figure Sierpinski described in 1915. The reason is arithmetic. Each cell is the sum, modulo 2, of the two cells diagonally above it, which is exactly how Pascal’s triangle is built. Color the odd entries of Pascal’s triangle black, leave the even ones white, and you have the rule 90 picture.

Rule 30 differs from rule 90 in a single place: it takes the left neighbor exclusive-or the middle cell or the right one. That one “or” breaks the arithmetic. The left edge of its triangle still shows stripes, but the interior looks like static. The column of cells directly under the starting cell begins 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1 and gives no sign of settling. Wolfram proposed that column as a source of random numbers, and it was used in Mathematica to make random integers.

How random is it, really? In 2019 Stephen Wolfram posted three prize problems about that center column. The first asks whether it ever becomes periodic. By then computation had shown no repeat within the first billion steps. What the problem asks for is a proof, and running the rule longer cannot supply one.

Wolfram tried to bring order to this in 1984. Starting many automata from disordered rows, he reported that they appear to fall into four classes: those that settle to one uniform state, those that leave separated stable or periodic structures, those that stay chaotic, and a fourth kind that grows complex localized structures, some of them long-lived. He compared the first three to limit points, limit cycles and chaotic attractors, and conjectured that the fourth is capable of universal computation. Among the elementary rules, the usual examples are rules 0 and 32 for the first class, 4 and 108 for the second, 30 and 126 for the third, and 110 for the fourth, with rule 54 beside it.

One conjecture became a theorem. Wolfram conjectured in 1985 that rule 110 can carry out any computation, and Matthew Cook’s proof appeared in 2004. The byte 01101110, given the right starting row, does whatever a computer can.

The classes are a description, not a derivation. Wolfram called them qualitative, and they were assigned by watching what the rules drew. David Eppstein, sorting the two-dimensional rules described below, has argued that two yes-or-no questions give a cruder but more objective classification. The eight bits do not announce their class; it was found by running them. For a rule that can compute, that is no accident. Wolfram’s own abstract says that if the fourth class is universal, properties of its behavior over unlimited time are undecidable.

Conway’s rule and its zoo

In October 1970 Martin Gardner’s column in Scientific American introduced a two-dimensional rule that John Conway called life. Each cell of a square grid has eight neighbors. A live cell with two or three live neighbors survives; with fewer it dies of isolation and with more of overpopulation. An empty cell with exactly three live neighbors comes alive. Every birth and death happens at once.

Conway chose those numbers after long experiment, to make the fate of a pattern hard to foresee: no simple proof that anything grows forever, patterns that seem to anyway, and small beginnings that churn for a long time before fading, freezing or cycling. Readers played it with counters on a board. Conway also had a PDP-7 with a screen.

The vocabulary came quickly. A pattern that never changes is a still life; a two-by-two block is one, and the beehive another. A pattern that returns to itself is an oscillator, and the number of generations it takes is its period. Three cells in a row, the blinker, has period 2. The pulsar has period 3, and Gardner already gave its three states as 48, 56 and 72 counters.

A pattern that returns to itself somewhere else is a spaceship. The five-cell glider is the first: after four generations it is the same shape one cell further along a diagonal. Conway called one cell per generation the speed of light, so the glider travels at a quarter of it, written c/4.

Conway conjectured that no finite pattern grows without limit, and offered a prize for a proof or a counterexample before the year was out. The counterexample came in November 1970. Bill Gosper’s glider gun, the first finite pattern known to grow forever, releases a new glider every 30 generations. It starts with 36 live cells; load it in the tool and the counter reads 41, 46 and 51 at generations 30, 60 and 90, five cells more for each glider in flight.

Then there is the R-pentomino, five cells in a three-by-three box. Gardner reported that Conway had tracked it for 460 moves without learning its fate. It settles only at generation 1103, with 116 cells, six gliders among them.

A family of rules and a way to trade patterns

Conway’s rule is one choice among many of the same shape. Say for each count from 0 to 8 whether an empty cell is born, and for each count whether a live cell survives, and you have filled 18 yes-or-no entries. That makes 2 to the 18th power, 262,144 rules, called Life-like. They are written with the birth counts after a B and the survival counts after an S, so Conway’s rule is B3/S23. HighLife, B36/S23, behaves much like it but has a small pattern that copies itself. In Seeds, B2/S, every live cell dies every generation, and most patterns explode all the same.

People who study these rules share patterns as text. The form the Golly simulator prefers is run-length encoding, a format created by Dave Buckingham. A header line gives the width, the height and the rule. After it, b is a dead cell, o a live one, a dollar sign ends a row, an exclamation mark ends the pattern, and a number in front of any of them repeats it. The R-pentomino is b2o$2o$bo! under the header x = 3, y = 3, rule = B3/S23. It can be copied out of an email and pasted straight into a simulator.

What the stack shows, and what it cannot

A one-dimensional rule keeps its own history: each generation is drawn under the last, and the page is a picture of time. A two-dimensional rule has no such page. The board shows one instant, and everything in the vocabulary above is a claim about many instants. So stack them. Put each generation on top of the one before and time becomes height. A block becomes a plain square column. A blinker becomes a column that turns a quarter turn at every floor. A glider becomes a staircase that climbs four floors for every step sideways, which is c/4 made into a slope you can measure with a ruler.

The stack is also an object, and here honesty matters. Stack a glider for 16 generations on a base plate, with cells 2 mm on a side, and the tool builds 410 square faces, 820 triangles, in a volume of 14 x 14 x 34 mm. It also reports 38 edges that belong to four faces instead of two, and 16 pieces: the staircase on its plate, and fifteen single cells that hang on it by an edge. In every generation one cell of a glider touches the rest only at a corner. The surface is closed, but it is not a strict solid, and whether a given slicer accepts it is something to test, not assume.

The other limit is the edge of the board. The figures for the R-pentomino belong to an endless plane, and no screen has one. On the tool’s largest board, 512 cells on a side with wrapped edges, the counter does read 116 at generation 1103. It holds there until generation 1182, when two gliders that left in different directions meet across the wrapped edge and collide. With empty edges a glider runs into the wall at generation 1065, and the count at 1103 is 113.

And no simulator proves a negative. The tool compares each generation with the 128 before it, which finds a pulsar at once and says nothing about a pattern whose period is 129. Running rule 30 for a billion steps did not settle whether its center column repeats. The card with eight lines is the easy part. What it means is in the stack, and the stack is never finished.