Cellular automata — the series
-
Eight rules and a triangle
A row of cells, each one deciding its next state from the three above it. Eight cases, one bit of output each — a rule that fits in a byte, and 256 of them in total. One of those bytes draws Pascal's triangle.
-
The rule that computes
One of the 256 elementary rules can run any program. Not simulate one, not approximate one — a machine that can compute anything computable, built from a lookup table with eight rows and nothing else.
-
A road where nobody overtakes
Rule 184 moves every 1 one cell to the right whenever the cell ahead is empty. It is one of only five elementary rules that never change the number of 1s, and that single property turns it into a model of traffic with an exact transition: below half density every jam dissolves, above it jams can never all clear and drift backwards against the flow.
-
No local rule can count the votes
A ring of cells, each holding 0 or 1, has to agree on whichever value is in the majority — every cell seeing only its neighbours. The best-known rule gets it right most of the time and wrong near a tie; no rule of any radius gets it right always. Yet two rules run one after the other do, on every ring, and the first of them is the traffic rule.
-
A jam that comes from nowhere
Give cars on a ring road a top speed of five cells a step, let each slow to the gap ahead, and add one more rule: now and then, at random, a driver eases off by one. That is the whole of the Nagel–Schreckenberg model, and it produces what the exactly solvable rule 184 could not — jams that form in free traffic with no obstacle, drift backwards against the flow, and cost the road more than a third of its capacity. Set the top speed to one and remove the chance, and it is rule 184 again, cell for cell.
-
A rule that remembers one row back
Only six of the 256 elementary cellular automata can be run backwards, and all six are trivial: shifts, copies and complements. Every interesting rule forgets. But make the new row depend on the row before the current one as well — combine the rule's output with it cell by cell — and every rule, rule 30 included, becomes exactly reversible: run forwards, swap the last two rows, run the same rule again, and the starting row comes back cell for cell. Nothing is lost, and yet the patterns still look as disordered as ever.
-
The column rule 30 will not explain
Start rule 30 from one live cell and read down the middle. The column has passed every test of randomness tried on it, and three plain questions about it are open: whether it ever repeats, whether its 1s make up half of it, and whether its n-th cell can be had without n steps of work. What can be measured says something about each — and the diagonals beside it are periodic, with periods that double going inwards.
-
The zero of a sandpile
Pile grains of sand on a grid, and whenever a cell holds four, let it topple and pass one grain to each neighbour. The order in which cells topple turns out not to matter, and the piles that keep recurring when sand is dropped at random form a group — one whose size is the number of spanning trees of the grid. Its zero is not the empty grid but a fractal picture of nested squares, and sand dropped on a single cell spreads into a round pile with the same kind of pattern inside.
-
An ant that builds a highway
Two rules: on a white cell turn right, on a black cell turn left, and flip the colour as you leave. From an empty grid the ant wanders for 9,975 steps without visible order, then falls into a cycle of 104 steps that carries it diagonally for ever. That it always escapes to infinity is proved; that it always ends on a highway is not.
-
The ash a random soup leaves
Fill a grid at random, apply Conway's rule — three neighbours give birth, two or three keep a cell alive — and the population collapses from half the cells to about three in a hundred, leaving scattered blocks and blinkers. Five cells in the shape of an R take 1,103 generations to do the same and peak at 319 on the way. The Game of Life is a universal computer, so nothing short of running it can say when a pattern will settle, and the figures run it.
-
A line that fires all at once
A line of soldiers, each knowing only its two neighbours and able to hold just a few states, must all fire at the same instant on an order given to the one at the end. No soldier can count, or knows the length of the line. Yet a rule table of seventeen states does it, tested on every line up to 300, by sending one signal three times as fast as another and letting them meet in the middle. The fastest possible rules do it in 2n − 2 steps, with six states; whether five can is still unknown.