Introduction

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.

Run the Rules

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">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">Rule 110 (Turing-complete)</button>
    <button type="button" data-rule="30">Rule 30 (Chaos)</button>
    <button type="button" data-rule="90">Rule 90 (Sierpiński)</button>
    <button type="button" data-rule="184">Rule 184 (Traffic)</button>
    <button type="button" data-rule="0">Rule 0 (All dead)</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Elementary Cellular Automaton
// Each cell is 0 or 1. At each step the new state of cell i is determined by
// the 3-bit pattern (left, center, right) = bits 2,1,0 of an index 0-7.
// The rule number (0-255) encodes the output for all 8 patterns.
const canvas = document.getElementById('ca');
const ctx = canvas.getContext('2d');
const W = canvas.width;   // 540px
const H = canvas.height;  // 360px
const CELL = 3;           // px per cell
const COLS = Math.floor(W / CELL);  // 180 cells across
const ROWS = Math.floor(H / CELL);  // 120 rows

const COLORS = { alive: '#1d3557', dead: '#f0f4f8' };

let rule = 110;

// Build the 8-entry lookup table for a given rule number.
function buildTable(r) {
  const t = new Uint8Array(8);
  for (let i = 0; i < 8; i++) t[i] = (r >> i) & 1;
  return t;
}

// Step one generation.
function step(row, table) {
  const next = new Uint8Array(COLS);
  for (let c = 0; c < COLS; c++) {
    const l = row[(c - 1 + COLS) % COLS];
    const m = row[c];
    const ri = row[(c + 1) % COLS];
    next[c] = table[(l << 2) | (m << 1) | ri];
  }
  return next;
}

// Describe the rule behavior.
const DESCRIPTIONS = {
  110: 'Rule 110 — Turing-complete. Persistent gliders collide to produce aperiodic structure.',
  30:  'Rule 30 — Chaotic. The right half looks statistically random; used in Wolfram’s Mathematica RNG.',
  90:  'Rule 90 — Sierpiński triangle. Each cell = XOR of its two neighbors (additive rule).',
  184: 'Rule 184 — Traffic model. 1s move right unless blocked; models single-lane jam formation.',
  0:   'Rule 0 — All cells always die. Trivial fixed point.',
};

function describeRule(r) {
  // Classify the rule by its table properties
  const t = buildTable(r);
  const sum = t.reduce((a, b) => a + b, 0);
  if (DESCRIPTIONS[r]) return DESCRIPTIONS[r];
  const zeros = t.filter(x => x === 0).length;
  if (sum === 0) return fmt('Rule %r% — All cells die (density 0).', { r: r });
  if (sum === 8) return fmt('Rule %r% — All cells live (density 1).', { r: r });
  // Check additive (XOR-based): rule 90, 150
  if (r === 150) return 'Rule 150 — Additive (XOR + center). Another fractal pattern.';
  return fmt('Rule %r% — %sum% of 8 neighborhood patterns produce a live cell.', { r: r, sum: sum });
}

function draw() {
  const table = buildTable(rule);

  // Seed: single live cell at center
  let row = new Uint8Array(COLS);
  row[Math.floor(COLS / 2)] = 1;

  ctx.clearRect(0, 0, W, H);

  for (let y = 0; y < ROWS; y++) {
    for (let x = 0; x < COLS; x++) {
      ctx.fillStyle = row[x] ? COLORS.alive : COLORS.dead;
      ctx.fillRect(x * CELL, y * CELL, CELL, CELL);
    }
    row = step(row, table);
  }

  document.getElementById('info').textContent = describeRule(rule);
}

// UI wiring
const slider = document.getElementById('ruleNum');
const label  = document.getElementById('ruleLabel');

function setRule(r) {
  rule = r;
  slider.value = r;
  label.textContent = r;
  document.querySelectorAll('.presets button').forEach(b => {
    b.classList.toggle('active', +b.dataset.rule === r);
  });
  draw();
}

slider.addEventListener('input', () => setRule(+slider.value));

document.querySelectorAll('.presets button').forEach(b => {
  b.addEventListener('click', () => setRule(+b.dataset.rule));
});

// Console verification: Rule 110 step from seed [0,1,0] pattern
// Pattern: ...0 1 0... -> neighborhood 010 = index 2 -> bit 2 of 110 = (110>>2)&1 = 1 ✓
console.assert(buildTable(110)[2] === 1, 'Rule 110 neighborhood 010 should give 1');
// Pattern: ...1 1 0... -> neighborhood 110 = index 6 -> bit 6 of 110 = (110>>6)&1 = 1 ✓
console.assert(buildTable(110)[6] === 1, 'Rule 110 neighborhood 110 should give 1');
// Pattern: ...1 1 1... -> neighborhood 111 = index 7 -> bit 7 of 110 = (110>>7)&1 = 0 ✓
console.assert(buildTable(110)[7] === 0, 'Rule 110 neighborhood 111 should give 0');
// Rule 90: each cell = XOR of neighbors => table[5]=0,table[3]=1,table[6]=1 etc
// table index 5 = 101 -> 1 XOR 1 = 0 ✓
console.assert(buildTable(90)[5] === 0, 'Rule 90 neighborhood 101 should give 0');
// table index 6 = 110 -> 1 XOR 0 = 1 ✓
console.assert(buildTable(90)[6] === 1, 'Rule 90 neighborhood 110 should give 1');
console.log('All Rule 110 / Rule 90 table assertions passed');

setRule(110);
Result
Console

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.

The Real Complexity

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)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/cellular-automata/Content licensed under CC BY-NC 4.0.