Topic · Computation

Rule 110

An eight-bit rule, provably universal.

One byte of rule, applied to a row of bits, is enough to encode any computation. The Simulator lets you change rule, seed and speed live.

→ Open the Simulator ← Back to the atlas

01101110₂ = 110₁₀

First encounter

Eight bits of rule. A whole universe.

The big idea

Draw a row of cells, each one black or white. Look at every cell with its two neighbours — three cells, eight possible patterns. A rule says, for each pattern, what the cell becomes next. Eight outputs. Eight bits. One byte. There are exactly 256 such rules — and one of them, Rule 110, is enough to do every computation a computer can do.

A concrete example

Write the eight neighbourhood patterns in descending binary: 111, 110, 101, 100, 011, 010, 001, 000. Under each, write the next-step output for Rule 110. Read the outputs as a single binary number — 01101110 — and convert: that is the decimal 110. The name is literally the rule.

patterns · 111 110 101 100 011 010 001 000

outputs · 0 1 1 0 1 1 1 0 = 110

Why it matters

In the late 1990s Matthew Cook proved at Wolfram Research that Rule 110 is Turing-complete; the result was finally published in 2004 after a long publication dispute. Arrange the right initial pattern and it can simulate any computer, any algorithm, anything you can compute. From eight bits. The simplest known universal cellular automaton — and arguably the simplest universal computer ever discovered.

Below: flip the eight output bits yourself, then watch the rule run live.

Section 01 · The 256 elementary rules

Wolfram's zoo, sorted into four classes

Stephen Wolfram catalogued every one of the 256 elementary cellular automata in the 1980s and noticed something striking: their long-run behaviour falls into four broad classes. Class 1 dies into uniform black or white. Class 2 settles into stripes or simple periodic patterns. Class 3 is pseudo-random — noise that never quite repeats. Class 4 is the rare and strange middle ground: islands of order drifting through noise, gliders colliding, structure that is neither periodic nor chaotic. Class 4 is where universality hides — and Rule 110 is its flagship.

The four Wolfram classes · single-cell seed

Class 1 · Rule 0 — dies

Class 2 · Rule 250 · filled

Class 3 · Rule 30 — chaos

Class 4 · Rule 110 — gliders

Section 02 · Reading the rule

From eight patterns to a single number

Every elementary rule looks at three cells (left, centre, right) and returns one bit. Eight possible 3-bit inputs, one output each — that is exactly a function from {0,1}³ to {0,1}, which is exactly 8 bits of information, which is one byte. Lay the outputs in Wolfram's canonical order — input 111 contributes the high bit, input 000 the low bit — and the byte you read off is the rule's number. Rule 30 outputs 00011110₂. Rule 110 outputs 01101110₂. The naming is not decorative; it is the rule.

111

110

101

100

011

010

001

000

0 1 1 0 1 1 1 0₂ = 110₁₀

Section 03 · Rule 30 vs Rule 110

Chaos and structure, side by side

Pick Rule 30 and the centre cell of an evenly-spaced row diverges into apparent randomness so good that Mathematica still uses Rule 30 as a pseudo-random number generator. Pick Rule 90 and the same seed paints a perfect Sierpiński triangle — pure recursive order. Rule 110 sits between them: a striped background woven through with dozens of triangular gliders that drift, collide, and recombine. It is neither chaos (like 30) nor crystal (like 90). It is, exactly, computation.

Same seed, three rules

Rule 30 — chaotic

Rule 90 — fractal

Rule 110 — computational

Interactive · the lookup table

Build any of the 256 rules with eight clicks

Each tile shows one of the eight neighbourhood patterns and the output bit it produces. Click any output to flip it. The binary string at the bottom updates live; its decimal value is the rule number. The presets jump you straight to four famous rules.

Lookup table · click any output bit

01101110₂ =110₁₀

Interactive · the simulator

Watch the rule you just built

The canvas runs the current rule for as many steps as the slider asks for, starting from a single centre cell or a random row. Edit the lookup table above and the picture redraws instantly — feel for yourself how dramatically one flipped bit can change everything.

Live evolution · current rule

rule 110

steps180

live · rule 110

binary · 01101110

decimal · 110

of · 256 total

Flip a bit in the table above and the canvas redraws instantly.

Section 04 · Gliders in Rule 110

Moving pieces, like Life but in one dimension

If you let Rule 110 run on a random row for a few hundred generations, recognisable shapes emerge: long left-moving stripes, short right-moving wedges, stationary blocks. Matthew Cook catalogued more than a dozen distinct glider species — A, B, C₁, C₂, D₁, D₂, E, F, G, H — each with its own speed and width. Glider collisions act as logic gates: the right pair produces a stable signal, the wrong pair annihilates. It is Conway's Game of Life compressed into one dimension, with the same emergent zoo and the same hint of computation.

Section 05 · Turing-completeness

Cook 2004 — universality from a byte

Matthew Cook's construction, completed at Wolfram Research in the late 1990s and finally published in 2004 after a lengthy publication dispute, shows that the glider zoo of Rule 110 can simulate a cyclic tag system — and cyclic tag systems are themselves Turing-complete. Any program, any computation, any algorithm can be encoded as an initial row of cells; Rule 110, applied long enough, runs that program. The proof took thousands of cells per logical step and is famously intricate, but the conclusion is clean: a one-line lookup table is a universal computer. No clock, no memory, no instruction set — just a rule.

Section 06 · Universality everywhere

Complexity from simplicity is a deep theme

Rule 110 is one entry in a longer ledger. Conway's Game of Life is Turing-complete; so is the Wang-tile system; so are billiard balls, soap films, and certain piles of dominoes. Wolfram's Principle of Computational Equivalence conjectures that, beyond a low threshold of complexity, essentially every system that is not obviously simple is computationally universal. Whether or not that conjecture survives, the empirical pattern is unmistakable: universality is cheap. Nature did not have to wait for transistors. A row of cells and a byte of rule were always enough.

Open the Simulator.

The full Simulator lets you switch palette, slow the time-step down to a crawl, jump to the eight most-studied rules, and seed the grid from the edge for asymmetric experiments. Everything you just played with, with more room to breathe.

→ Open the Simulator