Wolfram's Elementary Cellular Automata

1. Definition and encoding

An elementary cellular automaton (ECA) is a one-dimensional, two-state, three-neighbour cellular automaton. The universe is an infinite binary string — each cell holds either 0 (white) or 1 (black). At each discrete time step, every cell simultaneously updates its state according to a local rule that depends on the cell itself and its immediate left and right neighbours.

Because each neighbourhood consists of exactly 3 cells each holding one of 2 states, there are 2³ = 8 possible neighbourhood configurations. A rule must specify an output (0 or 1) for each configuration — giving 2⁸ = 256 possible distinct rules. Wolfram numbered these rules 0 through 255 using the binary encoding of the output bits:

This "Wolfram code" gives each rule a unique integer name. Rule 0 maps every neighbourhood to 0 (all cells die). Rule 255 maps every neighbourhood to 1 (all cells live forever). Rule 30 and Rule 110 are the famous examples at opposite ends of the complexity spectrum.

2. Reading a rule table

To decode rule N, write N in binary (8 bits). The k-th bit from the right (bit k) tells what output a neighbourhood of numeric value k produces.

Example for Rule 110 (binary: 01101110):

A standard visualization stacks time downward: row 0 is the initial condition (a single black cell on a white background is canonical), row 1 is after one step, row 2 after two steps, and so on. The resulting space-time diagram is the ECA's "picture", and its visual complexity is a direct proxy for the rule's dynamical complexity.

3. The four complexity classes

Wolfram's central empirical observation (later codified in A New Kind of Science, 2002) is that all 256 rules fall into exactly four qualitative classes, which he named Class I through Class IV. These classes appear to be universal: they recur in higher-dimensional automata, Turing machines, and other discrete computational systems.

The classification is robust but not sharp — there is no computable algorithm that assigns class membership (the halting problem is an obstruction). In practice, visual inspection of the space-time diagram and measurement of correlation lengths are used to classify rules.

Wolfram's conjecture is that Class IV systems in general — not just Rule 110 — are computationally universal. This remains unproven for most Class IV rules and is one of the central open questions in the theory of computation.

4. Notable rules: 30, 90, 110, 184

Rule 30 — chaos from simplicity

Rule 30 produces visually random Class III patterns from a single black cell. Its central column is statistically indistinguishable from a fair coin toss — Wolfram used it as the default random-number generator in Mathematica from 1986 to 2022. Diehard, NIST, and other test suites fail to detect non-randomness in the central column for billions of bits.

Rule 90 — Sierpiński triangle

Rule 90 is additive: new state = left XOR right (center is ignored). Starting from a single 1, the pattern is exactly Pascal's triangle modulo 2 — a perfect discrete Sierpiński triangle with fractal dimension log₂3 ≈ 1.585. Rule 90 is used in linear feedback shift registers and certain stream ciphers.

Rule 110 — universal computation

Rule 110 is the only elementary CA proven to be Turing complete (proved by Matthew Cook in 1994, published 2004). See Section 5 for details.

Rule 184 — traffic flow

Rule 184 is a minimal model of one-lane traffic. Cells represent road segments; state 1 = car present. Cars move right if the next cell is empty; otherwise they stay. The rule correctly reproduces: free-flow phase (density < 0.5), traffic jam formation, shock waves propagating backward, and conservation of car number. It is the simplest model that exhibits both phases of the Nagel-Schreckenberg traffic model.

5. Rule 110: proof of universality

Matthew Cook proved in 1994 (published after lengthy legal delays in 2004) that Rule 110 can simulate a cyclic tag system — a type of rewriting system known to be Turing complete. The proof is constructive: specific initial conditions encode a cyclic tag system, and the Rule 110 evolution faithfully simulates it.

Particles in Rule 110

Rule 110 space-time diagrams contain persistent moving structures called particles (gliders) embedded in a quasi-periodic background called ether. The ether is itself a period-14 pattern that tiles the background. Particles travel at various speeds (right-moving, left-moving, stationary) and interact with each other at well-defined collision points.

Cook's key insight was that the particle collisions in Rule 110 are rich enough to simulate logic gates — specifically, the tag system's append and delete operations. The ether acts as a "blank tape", and particles encode the data symbols.

Why is this surprising?

Rule 110 has exactly 8 binary degrees of freedom (the 8 rule bits). Any Turing machine can be reduced to it. This means that the question "does Rule 110 starting from initial condition X eventually produce a 1 somewhere in the pattern?" is undecidable — it is equivalent to the halting problem.

6. Outer totalistic and 2D generalisations

Elementary CAs consider the exact arrangement (left-center-right), not just the sum. A weaker class called outer totalistic rules depends only on the current center state and the sum of the neighbours. With a radius of 1 and 2 states, there are far fewer outer totalistic rules — but they generalise more naturally to 2D (where a Moore neighbourhood has 8 neighbours).

Conway's Game of Life as outer totalistic CA

Conway's Life is an outer totalistic 2D CA: the new state of a cell depends only on whether it is currently alive and how many of its 8 Moore neighbours are alive. The famous B3/S23 rule (birth on 3 neighbours alive, survival on 2 or 3 alive) is just one of 2¹⁸ = 262,144 outer totalistic 2D rules. Most are Class I or II; Life sits at the Class III/IV boundary and is also Turing complete.

Larger neighbourhoods

Wolfram extended the study to k-color, radius-r rules. For k=2, radius=2 (five-cell neighbourhood), there are 2³² ≈ 4 billion rules. The Wolfram code generalises accordingly: rule N maps neighbourhood configuration i to bit i of N. Some of these extended rules produce structures of comparable richness to Life in 1D.

Reversible CAs

A CA rule is reversible if every state has exactly one predecessor (no two states map to the same next state). Among the 256 elementary rules, only Rule 51 (complement) and Rule 204 (identity) are reversible. Toffoli and Margolus developed the block CA formalism specifically to construct reversible 2D rules, important for modelling physical time-reversibility.

7. JavaScript implementation

// Wolfram Elementary Cellular Automata — canvas renderer
// Supports any rule 0–255, configurable width and steps

const RULE_NUM  = 110;       // change to 30, 90, 184, etc.
const CELL_W    = 3;         // pixel width of each cell
const STEPS     = 200;       // number of generations to draw

// Pre-compute the 8-entry look-up table for the rule
function buildLUT(ruleNum) {
  const lut = new Uint8Array(8);
  for (let i = 0; i < 8; i++) {
    lut[i] = (ruleNum >> i) & 1;
  }
  return lut;
}

function runECA(canvas) {
  const lut   = buildLUT(RULE_NUM);
  const W     = Math.floor(canvas.width / CELL_W);  // cells per row
  const ctx   = canvas.getContext('2d');
  canvas.height = STEPS * CELL_W;

  // Initial condition: single 1 in the center
  let row = new Uint8Array(W);
  row[Math.floor(W / 2)] = 1;

  function drawRow(rowData, y) {
    for (let x = 0; x < W; x++) {
      ctx.fillStyle = rowData[x] ? '#a78bfa' : '#1e1e2e';
      ctx.fillRect(x * CELL_W, y * CELL_W, CELL_W, CELL_W);
    }
  }

  function step(current) {
    const next = new Uint8Array(W);
    for (let x = 0; x < W; x++) {
      const left   = current[(x - 1 + W) % W];
      const center = current[x];
      const right  = current[(x + 1) % W];
      const idx    = (left << 2) | (center << 1) | right;
      next[x] = lut[idx];
    }
    return next;
  }

  drawRow(row, 0);
  for (let t = 1; t < STEPS; t++) {
    row = step(row);
    drawRow(row, t);
  }
}

// Usage: call runECA(document.getElementById('ca-canvas'))
// Set canvas.width before calling (e.g., 600 for 200 cells at CELL_W=3)
        

Exploring all 256 rules

// Render all 256 rules in a grid (thumbnail size)
function renderAllRules(container) {
  for (let rule = 0; rule < 256; rule++) {
    const canvas = document.createElement('canvas');
    canvas.width  = 60;   // 20 cells × 3px
    canvas.height = 60;   // 20 steps × 3px
    canvas.title  = `Rule ${rule}`;

    const lut = buildLUT(rule);
    const W = 20, ctx = canvas.getContext('2d');

    let row = new Uint8Array(W);
    row[Math.floor(W / 2)] = 1;

    for (let t = 0; t < 20; t++) {
      for (let x = 0; x < W; x++) {
        ctx.fillStyle = row[x] ? '#a78bfa' : '#1e1e2e';
        ctx.fillRect(x * 3, t * 3, 3, 3);
      }
      const next = new Uint8Array(W);
      for (let x = 0; x < W; x++) {
        const idx = (row[(x-1+W)%W] << 2) | (row[x] << 1) | row[(x+1)%W];
        next[x] = lut[idx];
      }
      row = next;
    }
    container.appendChild(canvas);
  }
}
        

Performance note

The inner loop processes W cells per generation. For W = 1000 cells × 1000 generations, that is 10⁶ operations per render — fast enough for synchronous execution. For live interactive simulation (dragging rule slider), compute the entire space-time diagram once per rule change and cache it as an ImageData for fast repainting.

8. A New Kind of Science

Wolfram spent a decade on a comprehensive study of simple programs published as A New Kind of Science (NKS, 2002) — a 1,200-page monograph arguing that the physical universe is itself a kind of computation, and that the full range of natural complexity can arise from rules as simple as Rule 30.

The book's central thesis — the Principle of Computational Equivalence (PCE) — states that almost all processes that are not obviously simple are computationally equivalent (i.e., capable of universal computation). This would mean that biological evolution, fluid turbulence, and human thought are all in the same computational class.

NKS was controversial. The main scientific criticisms:

• PCE is unfalsifiable as stated — it says "almost all" systems are universal, with no criterion for exceptions.
• Most proofs are absent — many claims in the book are illustrated rather than proved, creating difficulty in separating conjecture from theorem.
• Prior work is underacknowledged — many results attributed to Wolfram had been published earlier by other researchers (Church, Turing, von Neumann, Ulam).
• Rule 110 was proved by Cook, not Wolfram — the attribution dispute mentioned in Section 5.

Despite the criticism, NKS did make major lasting contributions: a systematic taxonomy of simple programs, the popularisation of the computational-universe hypothesis, and the extensive documentation of the 256 ECA rules that remains the canonical reference.