Generator

Elementary cellular automaton, rule 90

A generator in the dynamics library, called 51 times across 10 essays. Below: what it draws with nothing chosen and at each mode an essay asks for, what it checks while drawing, and everywhere it is used.

automaton is one function. Everything below came out of it during this build, at parameters taken from the essays rather than invented for this page — so a figure here is the same figure a reader meets in an essay, and if the generator changes, this page changes with it.

With nothing chosen

Elementary cellular automaton, rule 90. A row of cells evolving downward, each cell decided by the three above it.

Traffic with random dawdling: jams from nowhere at density 0.18

A jam that forms in perfectly even traffic

How much traffic the road carries, with and without dawdling

Flow against density on a ring road

Speed limit one and no dawdling is rule 184

What it checks while it draws

Collected by running the family and recording what it asserted, not written here. The count is how many separate times the claim was put to the test while these drawings were made.

the word-parallel run agrees with the rule at step 1 ×200
running the same rule backwards returns the starting row exactly, cell 0 ×101
at step 1 the traffic rule and rule 184 agree in every cell ×69
after one lap the flux at density 0.025 is min(ρ, 1 − ρ) ×40
rule 90 row 0 matches Pascal's triangle mod 2 ×40
the ring of 3 returns after its period ×28
with no dawdling the flow at density 0.02 is min(5ρ, 1 − ρ) ×24
blocks of 1 are as even as a coin's would be ×12
every block of 1 appears ×12
every configuration of a 5-cell ring ends as its majority ×6
a density and a dawdling chance between 0 and 1 ×1
a density strictly between 0 and 1 ×1
a first-order rule can only lose rows, never gain them ×1
above half density at least 2k − n cars are always stopped ×1
adding the identity to the full pile and stabilising gives the full pile back ×1
after two hundred thousand steps the share of 1s is within three coin-toss standard deviations of a half ×1
an odd ring of 7 to 13 cells ×1
an odd ring, so there is always a majority ×1
and freezes with both values still present ×1
and the drawn ring ends as its majority ×1
at this density and dawdling some cars come to a halt ×1
below half density every jam is gone after at most one lap ×1
below one half the stopped share reaches zero ×1
between ten and four hundred topplings the avalanche sizes fall off as a power, with exponent near minus one ×1
each cycle moves the ant two cells diagonally ×1
every cell is on or off and nothing else ×1
every diagonal within 24 cells of an edge settles into a period within eight thousand steps ×1
every random start reached a highway within 300,000 steps ×1
every right-hand period is a power of two ×1
exactly five of the 256 rules conserve the number of 1s on every small ring ×1
far from one half it is always right ×1
from an empty grid the highway begins after about ten thousand steps ×1
more dawdling lowers the greatest flow the road carries ×1
near one half it is often wrong ×1
no elementary rule classifies every ring ×1
no grain reaches the edge: the pile keeps all 65,536 ×1
no two cars ever share a cell ×1
on the highway each 104-step cycle adds twelve black cells ×1
rule 184 never creates or destroys a car ×1
running the rule backwards returns the empty grid, the ant to the start, facing as it began ×1
stopped cars never fall below (2k − n)/n ×1
the backward run retraces the forward count step for step ×1
the dawdling traffic starts free and stops only later ×1
the drawn table reads back as the rule number ×1
the drawn triangle and the measured column agree ×1
the identity is not the empty pile: it holds grains everywhere except in a few regions ×1
the left-hand periods stay at four or less ×1
the local vote freezes within a few steps ×1
the number of rows is a whole number between 4 and 160 ×1
the pile holds a little over two grains a cell ×1
the pile stays inside the grid ×1
the recurrent piles are exactly as many as the spanning trees ×1
the right-hand periods never shrink going inwards ×1
the ring's length is a whole number between 20 and 240 ×1
the rule is a whole number between 0 and 255 ×1
the rule number is a whole number between 0 and 255 ×1
the second-order map sends different pairs of rows to different pairs ×1
the seed is single or random ×1
the start is random or one block of cars ×1
the steps drawn is a whole number between 10 and 160 ×1
the view is one the family draws ×1
toppling in two different orders gives the same final pile and the same number of topplings at every cell ×1
with no dawdling, evenly spaced cars never stop ×1

Where it is called

Every figure on this list is drawn by the same rule, so a change to the rule changes all of them at once. That is why the list is published.

Dynamics

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.

Dynamics

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.

Dynamics

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.

Dynamics

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.

Dynamics

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.

Dynamics

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.

Dynamics

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.

Dynamics

The orbit written as a word

Cut the interval in two and record which half each step of an orbit lands in. The orbit becomes an infinite string of two letters, the map becomes the act of deleting the first letter, and questions about trajectories turn into questions about words.

Dynamics

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.

Dynamics

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.

The whole library · What the figures prove