Rule 110

Imagine a row of cells, each either black or white. Every tick of the clock, each cell looks at itself and its two neighbors — three cells, eight possible patterns — and a lookup table of eight rules says what color the cell becomes next. That is all.

Rule 110 is one particular filling of that table, named by writing the eight outputs as a binary number: 01101110 in binary equals 110 in decimal. Stephen Wolfram catalogued all 256 such elementary cellular automata in the 1980s and noticed that Rule 110 produced strikingly complex, irregular patterns — neither the simple stripes of Rule 0 nor the pure chaos of Rule 30, but something in between: persistent glider-like structures that collide and interact.

In 2004, mathematician Matthew Cook proved what that complexity really meant: Rule 110 is Turing-complete. A universal computer — capable of running any program, deciding any decidable question — can be built from nothing but a one-dimensional strip of cells flipping by eight local rules. It is the simplest known system ever proven to reach that milestone. Related ideas about the halting problem apply directly: because Rule 110 is universal, predicting its long-run behavior is undecidable.

The demo below runs Rule 110 on a row of 80 cells with a single black cell as the starting seed. Each row displayed is one generation. Press Step to advance one generation at a time, or Run to animate continuously.

<div class="controls">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  <span class="gen-label">{{generation_label}} <span id="gen-count">0</span></span>
</div>
<canvas id="ca-canvas" width="560" height="360"></canvas>
<p class="hint">{{hint}}</p>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; background: #f5f7fa; color: #222; }
.controls { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.gen-label { font-size: .85rem; color: #555; margin-left: .4rem; }
#ca-canvas { display: block; border: 1px solid #cdd9e3; border-radius: 8px;
             cursor: crosshair; background: #fff; max-width: 100%; }
.hint { font-size: .82rem; color: #555; margin: .5rem 0 0; line-height: 1.5; }

// Code not found

Watch for the persistent triangular structures (called gliders in the literature) that slide leftward across the field. They are the key objects Cook used to build logic gates in his universality proof. Notice that the pattern never settles into simple repetition — this perpetual complexity is the hallmark of a Turing-complete system. Try Reset to start over, or edit the initial row by clicking cells.

How powerful is Rule 110, really?

• The rule table has just 8 entries. Every pattern of three cells maps to a single output bit. You can print the entire rule on a napkin.
• Yet it is Turing-complete. Matthew Cook's 2004 proof — accepted after a decade-long delay due to legal challenges from Wolfram's publisher — showed that Rule 110 can simulate a cyclic tag system, a known universal model of computation. That means Rule 110 can, in principle, run any algorithm: sort lists, compute digits of π, simulate other automata, or answer any question a Turing machine can answer.
• Predicting Rule 110 is undecidable. Because it is universal, there is no general algorithm that can determine whether a given initial configuration will ever reach a particular state. This is a direct corollary of the halting problem.
• It sits at the boundary of complexity classes. Wolfram's 2002 Principle of Computational Equivalence suggests that systems like Rule 110 — complex but not chaotic — are exactly where universality tends to appear. Rule 30 looks more chaotic but is not known to be universal; Rule 110 sits at the productive edge.
• Status: proven universal (Turing-complete), 2004, Matthew Cook.

The gap between Rule 110 and Rule 0 (all cells die) is the same gap explored by P vs NP: local simplicity versus global computational power.

Proving a tiny system universal has surprisingly broad consequences:

• Complexity theory: Rule 110 is the cleanest known example that universality can emerge from an almost trivially simple rule set. It sharpens our intuition for where the line between tractable and intractable lies.
• Artificial life and emergent computation: researchers study Rule 110's gliders as a model for how complex, self-sustaining structures arise from physics-like local interactions — without any designer encoding them.
• Cryptography and pseudorandomness: Rule 30, a close relative, generates sequences used in Mathematica's random-number generator. Understanding which automata are unpredictable matters for security.
• Physics and nature: some physicists argue that the universe itself may be a kind of cellular automaton. Rule 110 shows that if the local update rules are rich enough, the global behavior can be arbitrarily complex — a sobering hint about the limits of physical prediction.
• Teaching computation: Rule 110 is the starkest possible demonstration that you do not need a CPU, memory chips, or programming languages to get universal computation — just repetition of a local rule.

Once you have seen Rule 110, the boundary between "simple system" and "full computer" never looks the same again.

Rule 110 is the ultimate argument that complexity does not require complicated rules. A lookup table small enough to memorize in a minute produces behavior no algorithm can fully predict in general.

Matthew Cook's proof closed a chapter that Wolfram opened in the 1980s: the strange, never-settling patterns of Rule 110 are not artistic accidents — they are the fingerprint of universal computation hiding in one dimension. The next time you see a simple physical system produce surprisingly rich behavior, Rule 110 is a reminder that "simple" and "computationally limited" are not the same thing at all. Just as the halting problem shows that prediction has hard limits, Rule 110 shows those limits can be reached by the smallest possible machine.