ISEGORIA / MATH ENCYCLOPEDIA
Cellular automata: computation from local rules
Grids of cells that read only their neighbours and still compute, grow, and jam. The 256 elementary rules and their symmetries, Conway’s Life with its gliders and guns, Langton’s ant and the highway it builds after ten thousand chaotic steps, and rule 184 as a model of traffic with an exact fundamental diagram.
Before you begin: Logic and computability, and elementary probability
Predict, manipulate, then check your reasoning against the example and question. Graphs illustrate the mathematics; they do not replace a proof.
1. The 256 elementary rules
A row of cells, each 0 or 1, is updated all at once: the new value of a cell depends only on the old values of itself and its two neighbours. There are 2³ = 8 neighbourhoods, and a rule assigns each one an output, so there are 2⁸ = 256 rules; Wolfram numbers them by reading the eight outputs as a binary number, 111 first. The icons above the diagram are the rule itself: click any output to flip it. Time runs downwards. Rule 90 from a single cell draws the Sierpinski triangle, rule 30 looks random along its centre column, and rule 110 supports interacting particles and is Turing complete. Press Play to watch the rows appear.
Worked example. Rule 90 has outputs 01011010, so \(f(a,b,c)=a\oplus c\): each cell is the sum of its neighbours mod 2. From a single 1 the row at time \(t\) is the \(t\)-th row of Pascal’s triangle mod 2, and it holds \(2^{s(t)}\) ones, where \(s(t)\) is the number of ones in the binary expansion of \(t\). Rule 30 is \(f=a\oplus(b\lor c)\); its centre column begins 1, 1, 0, 1, 1, 1, 0, 0, 1, 1.
Watch out. The row wraps around, so a pattern that reaches the edge re-enters on the other side; from a single cell the width is chosen so that nothing wraps within the rows shown. Mirroring left and right, or swapping 0 and 1, changes the rule number but not the behaviour: the 256 rules fall into 88 equivalence classes, and the readout names the smallest number in the class. Wolfram’s four classes (uniform, periodic, chaotic, complex) are a description of typical behaviour, not a theorem: the same rule can behave differently from different initial rows, and deciding the class in general is undecidable.
Why are there exactly 88 essentially different elementary rules rather than 256?
Two symmetries act on rules without changing the dynamics up to relabelling: reflection, which swaps the roles of \(a\) and \(c\), and complementation, which swaps 0 and 1 in both inputs and outputs. Together they generate a group of order 4 acting on the 256 rules, and Burnside’s lemma counts the orbits: \((256+64+16+16)/4=88\), the four terms being the rules fixed by the identity, by reflection (\(2^6\), since the pairs 100/001 and 110/011 must agree), by complementation (\(2^4\)) and by their product (\(2^4\)).
2. Conway’s Game of Life
On a square grid each cell counts its eight neighbours. A live cell survives with 2 or 3 live neighbours and otherwise dies; a dead cell is born with exactly 3. Nothing else is specified, yet the rule supports a glider that walks diagonally one cell every four generations, an R-pentomino of five cells that grows for 1103 generations before settling, and Gosper’s gun, which fires a glider every 30 generations for ever. Click any cell to toggle it, then press Play; the graph on the right records the population. Change the rule to see how special B3/S23 is: Seeds explodes and Day & Night is symmetric under swapping life and death.
Worked example. A glider has 5 cells. After four generations the same five cells reappear shifted by one row and one column, so its speed is \(c/4\), a quarter of the light speed of one cell per generation. A block of 4 cells never changes: each live cell has exactly 3 live neighbours and each adjacent dead cell has at most 2. A blinker of three cells in a row turns into three in a column and back, period 2.
Watch out. The grid here is 64 by 40 and wraps at the edges, so a glider that leaves on the right re-enters on the left and can collide with what it left behind; Life is defined on the infinite plane, where the gun’s gliders escape for ever. The R-pentomino needs more room than this torus to reach its final population of 116, so here it settles differently. Life is Turing complete, which means that its long-term behaviour from an arbitrary pattern is undecidable: no formula gives the population at generation \(t\), only the computation does.
Why can nothing in Life travel faster than one cell per generation, and why is the glider slower?
A cell can only be born if a live cell already lies within its 3×3 neighbourhood, so the set of live cells grows by at most one cell in each direction per generation: that is the light speed \(c\). A pattern moving at \(c\) would have to be born on a fresh front every generation with exactly three parents there and leave nothing alive behind, and a closer look at what three parents on a front can do shows that no Life pattern can move faster than \(c/2\) orthogonally or \(c/4\) diagonally. The glider needs four generations to rebuild its shape one cell over, so it attains the diagonal limit exactly.
3. Langton’s ant
An ant stands on a grid of white cells. At each step it turns right on a white cell and left on a black cell, flips the colour of the cell it is on, and moves forward one cell. That is the whole rule, and it is reversible: run it backwards and the ant retraces its path. For about ten thousand steps the ant scribbles a symmetric-looking blob and then a chaotic mess; then, after about ten thousand steps, it starts building a highway, a diagonal band of period 104 that it extends for ever. Drag the step slider or press Play; the graph on the right counts black cells, and the readout says whether the highway has begun.
Worked example. Every step flips exactly one cell, so the number of black cells changes by \(\pm1\) and has the same parity as the step count: after 11,000 steps it is even. The highway repeats every 104 steps with a displacement of two cells diagonally, so once it is on the highway the ant’s distance from the origin grows by \(2\sqrt2\) every 104 steps, and the number of black cells grows by 12 per period.
Watch out. The grid is finite here, and the highway would eventually reach its edge; the slider stops well before that. What is proved about the ant is less than what is seen: the Cohen–Kong theorem says its trajectory is unbounded on any initial configuration with finitely many black cells, but that the highway always appears, on every finite start, is only a conjecture supported by every case tried. Change the starting pattern: from the black square the highway arrives after fewer than two thousand steps, while from the random patch a highway may set off, run into old debris, and dissolve back into chaos before the run ends.
Why must the ant’s path be unbounded, and why does that not prove the highway?
Suppose the ant stayed in a bounded region. Then the state (position, heading, colours of the finitely many cells) is finite, and a reversible map on a finite set is a permutation, so the motion is periodic. Colour the grid as a chessboard: the ant alternates between horizontal and vertical moves, so along its periodic path the cells fall into a consistent pattern in which the extreme corner cell would be visited from and left to the same side each time, forcing it to be entered only from one direction, which the turning rule forbids. So no bounded periodic motion exists. Unboundedness says the ant goes far, not how: a highway is one way to go far, and nothing rules out a slower, messier escape.
4. Rule 184 as traffic
Put cars on a ring road, one per cell at most, and let every car advance one cell per step if the cell ahead is empty. That is elementary rule 184, and it conserves cars. In the space–time diagram, time downwards, free-flowing cars are lines sloping right and a jam is a dark band whose front moves backwards, one cell per step, even though every car in it moves forward or not at all. The flow, cars passing a point per step, is plotted against density on the right: below density 1/2 every car eventually moves and the flow equals ρ; above it every gap moves backwards and the flow equals 1 − ρ. Drag the gold point to change ρ, or switch on random braking to see the exact triangle turn into the rounded curve of real roads.
Worked example. On a ring of 200 cells with 70 cars, \(\rho=0.35\). Within at most 100 steps the jams dissolve, every car moves every step, and the measured flow is exactly 0.35. With 130 cars, \(\rho=0.65\), the 70 gaps move backwards every step and the flow is exactly \(1-0.65=0.35\): the same flow, from a road full of stopped cars.
Watch out. Rule 184 has a maximum speed of one cell per step and no reaction time, so its fundamental diagram is a perfect tent and its jams never grow spontaneously: the peak flow 1/2 at \(\rho=1/2\) is a property of the rule, not of drivers. The Nagel–Schreckenberg model adds a random slowdown with probability \(p\): a moving car may brake for no reason. That single addition produces jams that appear out of free flow, a flow that depends on \(p\) and never reaches 1/2, and the scatter of real measurements. The flow shown is the mean over the last 100 steps, after a transient that is discarded.
Why does a jam move backwards when every car in it moves forwards?
Read rule 184 for the gaps instead of the cars: a gap moves one cell to the left exactly when the cell to its left holds a car, which is the mirror image of the rule for cars. So the empty cells are a second traffic stream flowing the other way at the same speed, and the front of a jam is where the gaps arrive. Above density 1/2 there are fewer gaps than cars, every gap always has a car to its left, so every gap moves every step and the flow is the gap density \(1-\rho\).