The rule that computes

Of the 256 elementary rules, one is a general-purpose computer.

That claim needs unpacking in both directions, because it is easy to hear as either weaker or stronger than it is. It does not mean rule 110 is efficient, or convenient, or that anyone would use it. It means that for any program on any computer, there is a starting row for rule 110 whose evolution carries out that program’s computation, and that no more powerful notion of computation exists to compare it against.

What the moving structures are #

The picture’s texture is a repeating background pattern, and the diagonal streaks are gliders: local configurations that reproduce themselves shifted sideways after a fixed number of steps.

A glider is not a thing the rule knows about. The rule is eight cases about three cells; nothing in it refers to a structure, a direction or a speed. The gliders are patterns that happen to be stable under the rule — arrangements which, when the rule is applied everywhere, reappear a few cells over. They are emergent in the strict sense: definable only in terms of the rule’s behaviour, not in its statement.

Rule 110 has a catalogue of them, each with a name and a velocity. Some move left, some right, some stand still. Crucially they collide, and a collision produces a definite output — sometimes annihilation, sometimes a different glider, sometimes several — determined entirely by which gliders met and at what phase.

That last fact is the whole of the construction. If gliders are signals and collisions are gates, then a wide enough row of carefully arranged gliders is a circuit.

It is worth noticing how little of this is visible in a picture sixty rows tall. A glider here has a period of several steps and travels a few cells per period, so sixty rows shows a handful of collisions and no structure larger than that. The constructions in the proof are wider than a screen and run for numbers of steps with many digits — the figures on this page show the material the proof is built from, at roughly the scale at which the material becomes visible at all, and nothing of the building.

The rule itself, read off its table #

Before any of that, it is worth seeing that rule 110 is not special-looking as a rule. It is eight bits like the other 255.

Read in words: a cell turns on unless all three of its neighbourhood are on, or all three are off, or only the left one is on. Three exceptions to “on”, and the rest follows. Nothing in that sentence suggests a computer, and no one reading it in 1983 could have said which of the 256 rules it was going to be.

Compare it to rule 90’s table, which is an exclusive-or and has a closed form for every cell. The two tables differ in three of eight entries. One has a formula; the other has an undecidable prediction problem.

What universality means #

The claim is that rule 110 is Turing complete: it can simulate any Turing machine, and therefore compute anything that can be computed at all.

The proof, by Matthew Cook around 1998 and published in 2004, goes through an intermediate: rule 110 simulates a cyclic tag system, a small formal model already known to be universal, which in turn simulates a Turing machine. The encoding is elaborate — a single tag-system step takes a large number of automaton steps and a wide stretch of cells — but it is exact.

The line of reasoning is worth stating because it is the standard shape of every universality proof: rather than build a computer, show that the system imitates something already known to be one. Universality is transitive, so a chain of simulations ending in a known-universal model is enough.

What it establishes is that the boundary between “can compute anything” and “cannot” does not lie where complexity of the rule would put it. Rule 110 has eight bits. A modern processor has billions of transistors. In terms of what is ultimately computable, they are equivalent, and the difference is entirely one of speed and convenience.

What the other classes cannot supply #

The three requirements below are easier to appreciate against rules that fail them, and the comparison is exact because every random-start figure on this page begins from the same row — the generator’s pseudo-random seed is fixed so that a build is byte-identical, which incidentally makes these controlled experiments.

Between “nothing moves” and “everything mixes” is where computation has to live, and that is the substance behind the informal talk of a boundary between order and chaos. A machine needs parts that stay put, parts that travel, and interactions between them — which is to say it needs the system to be neither rigid nor turbulent.

Whether that description picks out a class in any precise sense is unsettled. It is a good heuristic for where to look and it is not a theorem, and rule 110 is the one case where the looking paid off in a proof.

What a glider collision has to do #

The construction needs more than “signals exist”, and naming what it needs makes clear why fifteen years passed between the conjecture and the proof.

A computation needs three things, and the gliders have to supply all of them out of the same material.

Signals that persist. A glider must travel arbitrarily far without decaying, so that information can be moved from where it is produced to where it is used. Rule 110’s gliders do; most rules’ local structures do not, and a rule whose patterns fade after twenty cells cannot carry anything.

Interactions that are not trivial. Two gliders meeting must produce an outcome that depends on which two they were. If every collision annihilated both, there would be signals and no gates. Rule 110’s collision table has dozens of distinct outcomes, catalogued by hand.

A way to store state. Something must stay put and be modifiable, or the machine has no memory. Rule 110 gets this from stationary structures in the background pattern, which incoming gliders can convert from one form to another.

Each of those is a property nobody put in the rule, and each had to be discovered by looking at what the rule happened to do. That is why the proof is a construction rather than an argument — every gadget in it is an arrangement of gliders found by search, verified by running it, and fitted together like circuit parts whose specification was written after the parts were found.

The cost of that equivalence #

Universality is not free, and what it costs is the ability to answer questions about the system.

If rule 110 can simulate any program, then any question about rule 110’s long-run behaviour includes, as special cases, questions about arbitrary programs. And there are questions about arbitrary programs that no procedure can answer.

The standard one is the halting problem: no algorithm decides, for every program, whether it eventually stops. That is a theorem, proved by Turing in 1936, and it transfers directly. There is no algorithm that takes a rule 110 starting row and a cell and decides whether that cell is ever on. Not a slow algorithm, not an algorithm that needs a big computer — none.

So a question about a lookup table with eight rows is undecidable. The last essay noted that rule 30’s centre column might have no shortcut and that nobody has proved it. For rule 110 the corresponding statement is not a conjecture: prediction is provably impossible in general, by reduction to a theorem about computation.

That figure is the caveat the claim needs. Universality is a statement about what some starting rows do. Most starting rows do something unremarkable, and the ones that compute are constructed rather than found.

Where this sits with the rest of the field #

Three connections are worth drawing, because this result changes what the earlier essays were about.

It gives irreducibility a proof in one case. The last essay raised computational irreducibility as an observation — some rules seem to have no shortcut. For rule 110 it is a theorem: a shortcut for predicting arbitrary rule-110 evolutions would be a decision procedure for the halting problem, which cannot exist.

It separates two kinds of unpredictability. Sensitive dependence makes the future unknowable from an imprecise present, and improving the measurement buys steps. Undecidability is worse: the present here is known exactly — a row of bits, no rounding, nothing approximate — and the future is still unreachable by any method faster than running it.

It makes “simple” a useless predictor. A rule with 256 members contains one that is as computationally powerful as anything that will ever be built. Whatever separates the interesting rules from the dull ones, it is not the size of the rule — and since every rule here is the same size, size explains nothing about the difference between any two of them.

Why undecidable is a stronger word #

It is worth separating the two impossibility claims in this field carefully, because they are proved differently and they rule out different things.

Unpredictable — the chaotic case — means that the answer depends on more digits of the input than anyone has. Give the system exact input and prediction is straightforward: run it. The obstruction is measurement, and it is quantitative; the Lyapunov exponent says exactly how many steps a given precision buys.

Undecidable means something no amount of precision touches. The input here is exact — a finite row of bits, written down without error — and the claim is that no procedure whatever answers the question for all inputs. There is no quantity to improve and no resource that helps.

The proof of the second is not a physical argument at all. It is Turing’s diagonalisation: assume a halting-decider exists, build a program that consults it about itself and does the opposite, and derive a contradiction. The same move, applied to lists rather than programs, is what shows no list can contain every real number — and it is the reason both results feel like sleight of hand on first reading and neither is.

What transfers to rule 110 is the reduction. If a shortcut for rule 110 existed, encode a program as a starting row, apply the shortcut, and read off whether it halts. Since that decider cannot exist, neither can the shortcut. Nothing about cellular automata is used except the ability to encode.

What is not claimed #

The result attracts overstatement, and the overstatements are separable from it.

Not that rule 110 is a good computer. The encoding overheads are enormous — a single step of the simulated machine costs a great many automaton steps across a great many cells, and the blow-up is polynomial rather than constant. It is a proof of possibility and nothing else, and the question of whether the simulation can be made efficient is separate and was open for years after Cook’s construction.

Not that most starting rows compute. The universal behaviour requires a specific, elaborately constructed initial condition, with the program encoded into the spacing and phase of thousands of gliders. A random row almost certainly computes nothing in particular, in the same way that a random arrangement of transistors is not a processor.

Not that universality explains the picture. The visible texture of rule 110 is not evidence of computation happening; it is what the rule does. The theorem says something could be encoded there, not that anything is.

Not that undecidability applies to any particular row. The theorem is about the general question — no procedure works for all starting rows. Any specific row can still be settled by running it far enough, if it happens to settle, and most do. An undecidable problem is one with no uniform method, not one where every instance is hard.

Not that this settles Wolfram’s broader conjecture. The claim that almost all rules of sufficient complexity are universal remains a conjecture. Rule 110 is one rule that is, proved by one construction, and the proof gives no general method.

The mirror counts too #

Universality is a property of behaviour, not of a rule number, and the numbering has symmetries that carry it along.

The mirror of a universal rule is universal, and so is its on-for-off complement, so the property comes in groups of up to four. Rule 110’s group is {110, 124, 137, 193}, and the last essay’s count of 88 genuinely distinct behaviours is exactly the count of these groups.

That is worth knowing before reading any list of “the universal elementary rules”. There is one universal behaviour known among the elementary automata, presented four ways, and the temptation to read four entries as four discoveries is the same mistake as reading a rotated figure as a new one. A relabelling is not a result — which is the reason the directions a map leaves alone matter more than the coordinates a map is written in.

The order in which this was found #

The history is the same shape as the rest of this field, and by now the shape is the point.

Wolfram catalogued the 256 rules in 1983 by running them and looking. Rule 110 was picked out as the interesting one on visual grounds — it was neither periodic nor noise — and conjectured to be universal for no better reason than that it looked like it might be. The conjecture stood for fifteen years before Cook’s construction.

So the sequence was: draw everything, notice which one looks different, guess, and eventually prove. That is the sequence the Feigenbaum constant followed, and the Mandelbrot set, and in a different way the four-colour theorem. In each case looking came first and the theorem came second, which is unusual enough in mathematics to be worth stating as a pattern rather than as four coincidences.

It is also the argument for this site’s whole method. A figure is not an illustration of a result that already exists; sometimes it is the only way the result was ever going to be found.