Cellular Automata

Imagine a row of light bulbs, each either on or off. Every second, each bulb looks at itself and its two immediate neighbors — three bulbs in total — and flips according to a fixed rule. Then every bulb does the same thing simultaneously. That is a cellular automaton.

The idea sounds almost trivial: eight possible neighborhood patterns, eight binary outputs, just a lookup table. Stephen Wolfram catalogued all 256 such elementary cellular automata in the 1980s and discovered something remarkable. Most produce simple stripes or noise, but a few generate fractal-like triangles, aperiodic structures, and — in at least one case — full computational universality.

That case is Rule 110. In 2004, Matthew Cook proved that Rule 110 can simulate a Turing machine. A rule so simple it fits on a napkin can compute anything a modern supercomputer can. The catch: because Rule 110 is Turing-complete, deciding what it will eventually do — whether a given pattern ever appears, whether the automaton eventually halts — is undecidable.

Three neighbors. Eight bits. Unlimited power. And no algorithm that can predict the outcome in general.

Pick a rule number (0–255) and watch it evolve from a single live cell at the top. Each row is one generation; color shows which cells are alive. A few landmarks: Rule 110 grows structured, aperiodic patterns (Turing-complete). Rule 30 looks random — Wolfram used it as a pseudorandom number generator. Rule 90 draws the Sierpiński triangle.

<div class="controls">
  <label for="ruleNum">{{label_rule}}: <strong id="ruleLabel">110</strong></label>
  <input id="ruleNum" type="range" min="0" max="255" value="110">
  <div class="presets">
    <button type="button" data-rule="110">{{btn_110}}</button>
    <button type="button" data-rule="30">{{btn_30}}</button>
    <button type="button" data-rule="90">{{btn_90}}</button>
    <button type="button" data-rule="184">{{btn_184}}</button>
    <button type="button" data-rule="0">{{btn_0}}</button>
  </div>
</div>
<canvas id="ca" width="540" height="360"></canvas>
<div id="info" class="info"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; background: #fff; }
.controls { display: flex; flex-direction: column; gap: .5rem; margin-bottom: .6rem; }
label { font-size: .9rem; font-weight: 600; }
input[type=range] { width: 100%; accent-color: #1d3557; }
.presets { display: flex; flex-wrap: wrap; gap: .4rem; }
button { font: 600 12px system-ui, sans-serif; padding: .3rem .7rem;
         border: 1px solid #1d3557; background: #fff; color: #1d3557;
         border-radius: 6px; cursor: pointer; transition: all .1s; }
button:hover, button.active { background: #1d3557; color: #fff; }
canvas { display: block; width: 100%; max-width: 540px; height: auto;
         border: 1px solid #d0d7de; border-radius: 6px; }
.info { font-size: .82rem; color: #555; margin-top: .5rem; min-height: 2.4em; line-height: 1.4; }

// Code not found

Notice how dramatically different rules produce: stripes, triangles, apparent chaos. The same update width (three cells) and the same starting state can lead to completely different long-run behavior. For Rule 110, no shortcut exists — the only way to know what generation 10 000 looks like is to simulate all 10 000 steps.

How hard is predicting a cellular automaton? The answer depends on the rule.

• Simulating any automaton is easy: step through the grid generation by generation. Each step takes $O(n)$ time for a row of n cells.
• Predicting without simulating is a different question. For most rules you can find shortcuts — stripes are periodic, Pascal's triangle follows a closed formula. Simulation is not needed.
• Rule 110 is Turing-complete. In 2004, Matthew Cook proved this while working in Wolfram's group. By encoding gliders (persistent traveling structures) as signals and collisions as logic gates, Cook showed that Rule 110 can simulate any Turing machine. The result was so sensitive that Wolfram's company attempted to suppress publication until it appeared in 2004.
• Undecidability follows immediately. Because Rule 110 can simulate any Turing machine, any question about its long-run behavior that would hold for Turing machines in general is also undecidable here. In particular: given a starting configuration, will a specific pattern ever appear? This is equivalent to the Halting Problem — proven undecidable by Alan Turing in 1936. No algorithm can answer it for all inputs.
• Wolfram's computational equivalence. Wolfram conjectured that most rules that don't collapse to simple periodic behavior are also Turing-complete. The boundary between "predictable" and "computationally universal" runs right through the landscape of all 256 elementary rules.

The practical upshot: for a Turing-complete automaton, simulation is unavoidable. You cannot in general compress ten thousand generations into a formula. The universe, Wolfram argues, may work the same way.

The cellular automaton framework — local rules, synchronous updates, emergent global behavior — shows up across science and engineering:

• Conway's Game of Life: a 2D cellular automaton (not elementary, but the same idea) that is also Turing-complete and has inspired decades of research into self-replication and universal computation.
• Pseudorandom generation: Rule 30's chaotic output was the basis of Mathematica's built-in random number generator for years. Simple local rules can produce high-quality entropy.
• Fluid dynamics: lattice-Boltzmann methods model fluid flow as particles on a grid updating by local collision rules — a direct descendant of cellular automaton ideas, used in industrial simulation.
• Biology and pattern formation: Alan Turing's reaction-diffusion equations (1952) are continuous cousins of cellular automata. Spots on animal skin, shell patterns, and bacterial colony growth are all explained by local activation-inhibition rules.
• Cryptography: the nonlinear shift registers at the heart of some stream ciphers are effectively cellular automata. Rule 30 itself has been proposed as a hash component.
• Self-replicating machines: John von Neumann designed the first self-replicating automaton — a 29-state, 2D cellular automaton — in the early 1950s, decades before anyone spoke of nanotechnology.

All of this complexity emerges from one idea: give each cell a fixed rule, let them all tick simultaneously, and see what the universe computes.

A row of cells, each watching three neighbors and following a lookup table: that is everything Rule 110 does. Yet that is enough to simulate any computer ever built or imagined. And because it can simulate any computer, no algorithm can predict its long-run behavior — the question is exactly as hard as the Halting Problem.

Cellular automata teach two lessons at once. First, complexity does not require complicated rules — it can emerge from the simplest possible local interactions. Second, emergence and undecidability are two sides of the same coin: the moment a system is powerful enough to surprise you, it is likely too powerful for any shortcut to tame.

The next time you stare at the fractal triangles of Rule 110, remember: those patterns are not decorative. They are a proof that the universe can build a computer from almost nothing — and that some questions about what it will do next are unanswerable in principle.