Rule 110
The simplest system proved capable of universal computation
A repeating background with localised structures drifting through it and colliding. Proved capable of universal computation in 2004.
How it works
In plain English, before the notation
Rule 110 settles into a repeating background texture, and against that background it supports narrow structures that drift at different speeds. When two of them meet, the collision produces something new — sometimes a different structure, sometimes several, sometimes nothing. Those collisions are enough to carry out any computation at all, which was proved in 2004 and makes this the simplest system known to be capable of it.
Find the particles
- Open Presets and load "Rule 110 Particle Collisions" and press Play.
- Look past the repeating background and find the narrow diagonal structures moving through it at different angles.
- Watch where two of them meet. The collision is the computation — every gate in the universality proof is built from one.
Starting configurations
Loads straight into the simulatorTry any rule
The catalogue covers a few dozen rules. Here you can run any of the 262,144 two-state grid rules, or any of the 256 one-dimensional rules, including ones nobody has written up.
The number is the eight-entry lookup table below, read as a binary number.
Lookup table (01101110) — neighbourhood above, result below
Classification: Class 4 — localised structures against a repeating background
How it runs: the automaton is a single row. Each cell reads the three cells above it and looks up the answer in 01101110. The canvas is the history — each row is one step later than the one above it.
Well-known rules
Where it came from
Wolfram conjectured in the 1980s that Rule 110 was capable of universal computation, on the strength of its behaviour rather than any construction. Matthew Cook worked out the proof while at Wolfram Research; it was presented in 2004 and shows that Rule 110 can simulate a cyclic tag system, which in turn can simulate any Turing machine.
The result is significant because of how little Rule 110 has to work with: two states, three cells of context, and an eight-entry table. Nothing simpler has been shown to be universal.
The rule, precisely
What each cell looks at
Three cells on the previous row: (x−1, x, x+1)
What a cell can be
Two states per cell on a single row
The update
Rule 110 = 01101110 in binary, read over the patterns 111 down to 000
Class 4 in Wolfram’s scheme: neither settling into repetition nor dissolving into noise, but supporting persistent localised structures against a periodic background. Class 4 is where universality is found when it is found at all.
A background, particles, and collisions
The rule has a vocabulary that has been catalogued in detail:
- The background is a fixed repeating texture, sometimes called the ether. Everything else is defined relative to it.
- More than a dozen distinct localised structures are known, each moving at its own speed relative to the background.
- When two meet, the outcome depends on which structures they are and how they are aligned. The catalogue of collision outcomes is what the universality proof is built from.
- The construction is workable but extremely inefficient: simulating a simple computation this way takes an enormous number of steps.
Proved universal by Matthew Cook
Cook showed that Rule 110 can simulate a cyclic tag system, and cyclic tag systems can simulate any Turing machine. Rule 110 can therefore compute anything that is computable.
Computation is not rare
The lasting implication is that universal computation does not require a complicated substrate. If a rule this small can do it, then the property is probably widespread in physical systems that nobody built with computation in mind. That claim — Wolfram calls it the principle of computational equivalence — is a conjecture, not a theorem, but Rule 110 is its strongest single piece of evidence.
Things to try
- Use the Seed Row tool to inject a small disturbance into a running pattern, and follow it downwards to see which structures it produces.
- Start from a random row rather than a single cell — random starts produce far more collisions to watch.
- Reduce Speed in Settings and use Step (.) through a collision. Most of the interesting behaviour is over in a handful of rows.