Rule 110, Living — Elementary CA Zoo

Section 1

Watch ether settle

Start from random noise and let Rule 110 run for 220 generations. Within ~50 steps the chaos resolves into a diagonal stripe — the ether. A 14-cell repeating pattern, cycling every 7 generations. Gliders are what remain after the ether takes hold: local disturbances that didn't dissolve.

The ether pattern is 00010011011111. Every Rule 110 universe with a large enough domain eventually settles into this background, with occasional gliders riding through it. Re-roll to see different random seeds produce the same convergence.

Section 2

Three gliders, one collision

Three structures from Cook's catalog, hand-placed into an ether background and left to evolve for 200 generations. Coloured labels at the top mark each structure's starting position:

B-like glider — drifts rightward ~2 cells every 3 generations (sequence 0001110111 in ether)
A-like glider — drifts leftward ~8 cells every 30 generations (sequence 1001111 in ether)
Stationary structure — period-7, doesn't move (sequence 111 in ether)

Honest note: these templates follow the period and direction of Cook's catalog structures as documented in Cook (2004) and the Wikipedia summary. The placement shown here is schematic — the exact bit sequences are placed into a tiled ether background, but this is not a bit-for-bit reproduction of a verified Cook-catalog collision. What you see is genuine Rule 110 behavior; the specific interaction outcome may differ from Cook's computed collision tables.

Section 3

From gliders to computation

Gliders collide. Collisions produce new structures — sometimes a different glider, sometimes annihilation, sometimes a stationary residue. Cook's insight was that this collision algebra is rich enough to implement a cyclic tag system, and cyclic tag systems are Turing-complete.

How does a cyclic tag system work, and how does Rule 110 run one?read in layers

Start here A cyclic tag system is a simple tape machine. You have a tape of 0s and 1s and a fixed list of short strings called productions. At each step, you look at the leftmost tape symbol. If it's a 1, you append one of the productions to the right end of the tape. If it's a 0, you append nothing. Either way, you delete the leftmost symbol and advance to the next production in the list. Repeat forever. Despite how simple that sounds, cyclic tag systems can compute anything a Turing machine can.

High school More precisely: the system cycles through productions p₀, p₁, …, p_n−1 in order, wrapping around. At step t, production p_{(t mod n)} is active. If the leftmost tape symbol is 1, append p_{(t mod n)} to the tape; if 0, don't. Drop the leftmost symbol regardless. Cook showed (in the same 2004 paper) that any 2-tag system can be encoded as a cyclic tag system, and 2-tag systems are known to be Turing-complete (Cocke and Minsky, 1964).

Undergrad Cook's encoding of a cyclic tag system into Rule 110 uses sequences of A-gliders to represent tape symbols (a cluster of A-gliders = a 1; absence = a 0) and sequences of B-gliders to delimit production boundaries. When a tape symbol glider encounters a production marker glider, their collision either produces a new glider (appending a production symbol) or annihilates (appending nothing). The stationary structures serve as spacers and timing anchors. The full encoding requires the ether to extend over a huge spatial region — the initial conditions for any non-trivial computation are enormous.

Going deeper The completeness proof chain is: Rule 110 emulates cyclic tag systems → cyclic tag systems emulate 2-tag systems → 2-tag systems emulate Turing machines. Each step introduces overhead. Cook's original construction has exponential time blowup (Turing machine tape encoded in unary in the CTS, CTS encoded at huge scale in Rule 110). Neary and Woods (2006) showed that replacing 2-tag systems with clockwise Turing machines reduces the overhead to polynomial — a significant improvement, but still slow. The canonical reference for the full construction is Cook (2004), Complex Systems 15(1): 1–40, doi:10.25088/ComplexSystems.15.1.1.

Section 4

What this proves, what it doesn't

The proof establishes

There exists no algorithm that can predict arbitrary long-run Rule 110 behavior — the halting problem applies directly.
A two-state, three-neighbour, one-dimensional cellular automaton is computationally universal: it can simulate any Turing machine.
Rule 110 is, in this precise sense, the simplest known universal computer among elementary CAs — and among the simplest known anywhere, with 2 states and a 3-cell neighbourhood (6 binary input combinations producing one output bit).

The proof does not establish

That Rule 110 simulations are efficient. The CTS encoding is enormous and the simulation runs at exponential slowdown. Universality is about capability, not speed.
Anything special about edge-of-chaos or Langton's λ parameter. Rule 110 has λ = 5/8 = 0.625; many non-universal rules share similar λ values. λ is a statistical hint, not a universality detector.
That "complex-looking" rules are more likely to be universal. Rule 30 looks chaotic; it is not known to be universal. Rule 110 looks structured; it is. Appearance is not the classifier.

Why does the proof need such huge initial conditions?read in layers

Start here To compute anything, the CTS encoding needs to represent the entire input tape as a spatial arrangement of gliders. Even a small computation requires the gliders to be spread far enough apart that collisions happen in the right order. The upshot: a Rule 110 "computer" that runs a simple program might need an initial configuration millions of cells wide.

High school This isn't a flaw in the proof — it's an expected consequence of the encoding chain. Every step (CTS → 2-tag → Turing machine) introduces overhead. The proof is an existence proof: it shows that computation is possible in Rule 110, not that Rule 110 is a practical computer. The same caveat applies to most "simple" universal systems (e.g., Conway's Game of Life, Wang tiles, some chemical reaction networks).

Undergrad Neary and Woods (2006), "P-completeness of Cellular Automaton Rule 110," reduced the overhead to polynomial by changing the encoding chain. Their construction uses clockwise Turing machines directly instead of routing through 2-tag systems. Still not efficient, but an asymptotically better bound. The underlying point stands: universality has nothing to do with computational efficiency, and confusing the two is a common error in popular accounts.