Complexity · Computation · Discrete Math
📅 April 2026 ⏱ ≈ 13 min read 🎯 Beginner–Intermediate

Wolfram Cellular Automata & Complexity from Simple Rules

A cellular automaton updates each cell's state based solely on its neighbours — yet from a handful of bits of local rule, global structures emerge that range from static crystals and simple repetition to chaotic randomness and universal computation. Stephen Wolfram's systematic survey of all 256 elementary rules revealed that complexity is everywhere, not the exception. This article builds the theory from binary cells to Turing-complete automata and the Game of Life.

1. Elementary Cellular Automata — the 256 Rules

An elementary cellular automaton (ECA) consists of a 1-D row of cells, each holding a binary state (0 or 1). At each time step every cell is updated simultaneously using the same rule applied to the cell and its two neighbours. Since there are 2³ = 8 possible neighbourhood configurations and 2 possible outputs per configuration, there are exactly 2⁸ = 256 distinct rules.

neighbourhood: (left, centre, right) ∈ {0,1}³ — 8 combinations: 111 110 101 100 011 010 001 000 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ output bit7 … bit0 → encodes the rule number in binary

Rule 30: 30 = 00011110₂ 111→0 110→0 101→0 100→1 011→1 010→1 001→1 000→0

This Wolfram code numbering scheme (1983) gives each rule a unique integer 0–255. Rules are drawn by evolving from a single-cell seed and plotting each generation as a row. Time flows downward; the resulting pattern is the "spacetime diagram" of the automaton.

2. Wolfram's Four Complexity Classes

Wolfram classified all 256 elementary rules (and CA in general) into four qualitative classes based on their long-term behaviour:

Class I — Uniformity

All cells evolve to a single fixed state. Any initial condition collapses to a homogeneous background. Example: Rules 0, 8, 32, 40.

Class II — Periodic / Stable

Cells settle into simple periodic or stable patterns. Localised structures persist unchanged or cycle. Example: Rules 4, 19, 50.

Class III — Chaotic

Aperiodic, seemingly random patterns. Arbitrarily small changes to initial conditions lead to completely different patterns. Example: Rule 30, 45, 73.

Class IV — Complex

Long-lived, non-periodic, localised structures that interact in complex ways. Associated with computation and universality. Example: Rules 54, 106, 110.

Class IV behaviour — at the boundary between order and chaos — is associated with computational universality. The "edge of chaos" hypothesis proposes that life and cognition similarly operate at this boundary.

3. Notable Rules: 30, 90, 110

Rule 30 — Chaos and Random Number Generation

Starting from a single live cell, Rule 30 produces a chaotic irregular pattern. The output of the centre column is statistically random (passes most standard statistical tests). Wolfram used Rule 30 as a built-in pseudorandom generator in Mathematica and Wolfram Language. Nature implements something similar: the shell pattern of the cone snail Conus textile is a nearly perfect visual realisation of Rule 30.

Rule 90 — Pascal's Triangle mod 2

Rule 90 (XOR of the left and right neighbours, ignoring the centre) produces the Sierpiński triangle pattern. Starting from a single cell, the pattern at row n is precisely Pascal's triangle reduced modulo 2 — row n has a 1 wherever the binomial coefficient C(n, k) is odd.

Rule 110 — Universal Computation

In 2004 Matthew Cook proved Rule 110 is Turing complete: it can simulate any Turing machine. This requires an infinite initial condition encoding the program, but the result is profound — a rule described by a single byte can perform arbitrary computation. Rule 110 is the simplest known Turing-complete system.

4. Two-Dimensional and Totalistic Automata

In 2-D CA, cells sit on a grid (typically square or hexagonal). The update rule depends on the cell's own state and some neighbourhood. Two classic neighbourhood shapes are:

A totalistic rule depends only on the sum of neighbour states, not their arrangement. This reduces the rule space from 2^(2^9) to a much smaller set indexed by birth/survival counts — making systematic exploration feasible.

5. Conway's Game of Life

Introduced by John Conway in 1970, the Game of Life is a 2-D binary totalistic CA with Moore neighbourhood and the following birth/survival rules:

B3/S23: A dead cell becomes alive if it has exactly 3 live neighbours (Birth) A live cell survives if it has 2 or 3 live neighbours (Survival) All other cells die or remain dead (underpopulation / overcrowding)

From these three rules, an extraordinary menagerie of structures emerges:

6. JavaScript: ECA and Game of Life

Elementary Cellular Automaton

// Draw an ECA spacetime diagram on a canvas (ruleNum 0-255, width W, height H)
function drawECA(canvas, ruleNum, W = canvas.width, H = canvas.height) {
  const ctx = canvas.getContext('2d');
  ctx.fillStyle = '#000';
  ctx.fillRect(0, 0, W, H);

  const rule = ruleNum.toString(2).padStart(8, '0');   // '00011110' for rule 30
  const lookup = [...rule].reverse();  // lookup[neighbourhood_int] → output bit

  let row = new Uint8Array(W);
  row[Math.floor(W / 2)] = 1;   // single cell seed in centre

  ctx.fillStyle = '#fff';
  for (let y = 0; y < H; y++) {
    for (let x = 0; x < W; x++)
      if (row[x]) ctx.fillRect(x, y, 1, 1);

    const next = new Uint8Array(W);
    for (let x = 0; x < W; x++) {
      const L = row[(x - 1 + W) % W];
      const C = row[x];
      const R = row[(x + 1) % W];
      next[x] = +lookup[(L << 2) | (C << 1) | R];  // pack 3 bits → index
    }
    row = next;
  }
}

Game of Life (toroidal grid)

class GameOfLife {
  constructor(W, H) {
    this.W = W; this.H = H;
    this.grid = new Uint8Array(W * H);
  }

  set(x, y, v) { this.grid[y * this.W + x] = v; }
  get(x, y) { return this.grid[y * this.W + x]; }

  step() {
    const { W, H } = this;
    const next = new Uint8Array(W * H);
    for (let y = 0; y < H; y++) {
      for (let x = 0; x < W; x++) {
        let n = 0;
        for (let dy = -1; dy <= 1; dy++)
          for (let dx = -1; dx <= 1; dx++)
            if (dx || dy)
              n += this.get((x + dx + W) % W, (y + dy + H) % H);
        const alive = this.get(x, y);
        next[y * W + x] = (alive && (n === 2 || n === 3)) || (!alive && n === 3) ? 1 : 0;
      }
    }
    this.grid = next;
  }
}

Try it live

Run Game of Life on an interactive canvas — draw patterns, watch gliders, and explore oscillators in real time.

Open simulation →

7. Cellular Automata as Computers

Cellular automata can be viewed as massively parallel computers: every cell executes the same instruction simultaneously. This parallel nature makes them natural candidates for:

NKS — A New Kind of Science (Wolfram, 2002) argues that the computational universality found in Rule 110 and similar systems implies that nature at large is most simply modelled by CA-like local update rules rather than differential equations — pointing toward discrete, rather than continuous, foundations of physics.

8. Applications in Science and Art

Biology and Pattern Formation

Alan Turing's 1952 reaction-diffusion model produces animal coat patterns (leopard spots, zebra stripes) via a CA-like mechanism: activator and inhibitor chemicals diffuse and react locally. Continuous-time lattice models closely mirror true biological pattern formation.

Traffic Simulation

The Nagel-Schreckenberg model is a 1-D CA that reproduces traffic jams without any central control — jam wave formation emerges from local acceleration, braking, and random dawdling rules. Extended 2-D versions underpin city-scale microscopic traffic simulators.

Procedural Texture Generation

Artists and game developers use CA to generate organic textures: Rule 30 for randomness, 2-D cave/dungeon generation via "birth 3 / survival 2–3" smoothing, and crystal growth simulations via DLA (Diffusion Limited Aggregation).