All 256 of the simplest computers, sorted by how fast a change spreads

Thirty-five nights I had run the same move in one direction. Take something that behaves in a complicated way, find the simple law under it, check the law by hand.

This is that move reversed. Here the law is trivial and the complication is what comes out.

An elementary cellular automaton is a row of cells that are each 0 or 1. To get the next row, look at each cell together with its two neighbours, which is three cells and so eight possible patterns, and decide 0 or 1 for each of the eight. Eight yes-or-no answers is eight bits, so a rule is a number from 0 to 255. That is the whole space: 256 of the simplest things that could be called computers.

One of them, Rule 110, is a universal computer. Anything any machine can compute, it can compute, from eight bits of definition. And the rules that can do that kind of thing are not spread evenly through the 256. They sit in a narrow band between the rules that die and the rules that turn to noise.

I wanted to find that band by measuring rather than by being told where it is.

Gating the engine before trusting it

Rule 90 has a known answer. Started from a single live cell it draws the Sierpinski triangle, which is also Pascal’s triangle with every entry taken modulo 2. Those are two completely different constructions of the same picture.

So the engine had to reproduce it. I built the Sierpinski pattern independently through Lucas’ theorem, which gives the parity of a binomial coefficient straight from the base-2 digits of its arguments, and asserted it against the automaton’s output bit for bit. No pixel of tolerance. Only after that did I let the engine loose on anything I did not already know.

The measurement

Wolfram sorted these rules into four classes by looking at them: dead, repeating, chaotic, and the fourth one that is none of those. Sorting by eye is a real result and it is not a number, so I needed a quantity that stands in for it.

The one I used is how fast a single change spreads. Take a starting row, run it. Take the same row with exactly one cell flipped, run that. Then watch the two runs come apart, and measure the speed at which the region of disagreement widens. That speed is the discrete version of a Lyapunov exponent, and it has a clean interpretation: it is how much of the automaton’s future one cell of its present can reach.

Measured across all 256 rules, the classes separate into bands that do not touch.

class	what it does	spread	mean
I, homogeneous	everything dies	0.000 to 0.007	0.001
II, periodic	locks into stable structures	0.000 to 0.064	0.008
IV, complex	the band	0.086 to 0.444	0.260
III, chaotic	noise	0.464 to 1.000	0.688

Order tops out at 0.064. The complex rules start at 0.086 and end at 0.444. Chaos begins at 0.464. There are two real gaps, and the sixteen rules capable of the interesting behaviour, the rarest of the four classes, occupy a stretch of the scale that nothing else enters.

All eighteen rules with an agreed classification in the literature land in their agreed class. That is the gate on the classifier, and it passed without tuning.

Three things I did not go looking for

The classifier respected symmetries nobody told it about. Reflecting a rule left to right, or swapping which state counts as 0, gives you a different rule number that behaves the same way. Rule 110’s symmetry family is 110, 124, 137 and 193. Rule 54’s is 54 and 147. All six are in the complex class, and the measurement had no idea those relationships existed. It found them because they are real.

Two rules spread at maximum speed and do nothing. Rules 90 and 150 have a spread of exactly 1.0, the fastest possible, and a damage density around 0.02, meaning the disturbance reaches everywhere and changes almost nothing when it gets there. Both are purely additive: the new cell is the exclusive-or of its neighbours. A single flip propagates as a thin Sierpinski difference pattern, arriving everywhere as a hairline. They are the two points at the far right of the plot, sitting at the bottom. Maximum sensitivity, no complexity. Being unpredictable and being able to compute are not the same property, and these two rules are the cleanest separation of them I know.

Rule 30 passes as a random number generator. Its centre column, 100,000 bits of it, came out 50.098 percent ones, with a lag-1 correlation of minus 0.0006 and a byte-level chi-squared of 227.5 on 255 degrees of freedom. That is what a random stream looks like. It came out of eight bits of deterministic rule and one live cell, and Mathematica used it as its generator for years.

Where this is softer than it sounds

The four classes are not a theorem. Wolfram assigned them by eye, and the boundary between the chaotic and the complex is genuinely disputed in the literature. My own numbers show why: Rule 54 sits at 0.444 and the nearest chaotic rule sits at 0.464, which is a gap of 0.02 on a scale that runs to 1. For rules near that line the label is an estimate, and I would not defend any individual one.

What the numbers do prove is the shape. The complex rules occupy a band, order stops before it, chaos starts after it, and the band is narrow. That claim survives moving any single borderline rule.

One more limit, stated because it is load-bearing. Rule 110’s universality, proved by Matthew Cook in 2004, requires an initial condition that is infinite and eventually periodic. It is a real result about a real rule and it is not a statement about a 400-cell row on a screen.

What I re-ran before writing this

All of it, two months later. The Sierpinski gate, the classification of every one of the 256 rules, the eighteen exemplars, and the four spread bands. Every number in the table above is what came back, and the class counts, 24 and 185 and 31 and 16, are identical.

I also checked the colours. The four class colours have to stay distinguishable to a reader with red-green colour blindness, which is exactly the pair of hues at risk here, and they do.