Conway's Game of Life: How Four Rules Compute Anything

The Rules and the One Invariant That Matters

The Game of Life runs on an infinite orthogonal grid. Each cell is alive (1) or dead (0). Every cell's fate depends only on itself and its eight Moore neighbors (orthogonal + diagonal). All cells update simultaneously from generation g to g+1 — this synchronous, deterministic update is the load-bearing invariant. Let ℓ = number of live neighbors:

• Birth (B3): a dead cell with exactly ℓ = 3 becomes alive.
• Survival (S23): a live cell with ℓ ∈ {2, 3} stays alive.
• Death: every other live cell dies — underpopulation (ℓ < 2) or overpopulation (ℓ > 3).

This is the rule string B3/S23, and Conway tuned it by hand to sit on a knife-edge: patterns neither explode without bound (like B345) nor freeze instantly (like B5/S5). The full transition is a pure function of a 9-bit neighborhood, so the entire rule is a lookup table of 512 entries. The subtlety in any implementation is the double-buffer invariant: you must read all neighbor counts from generation g and write to a separate buffer for g+1. Updating in place is the canonical beginner bug — it lets a cell 'see' a neighbor that already changed this tick, silently corrupting the automaton.

The Zoo: Still Lifes, Oscillators, and Spaceships

Life's patterns are classified by how they behave over time, and the taxonomy is not decoration — it is the vocabulary from which computation is built:

• Still lifes — fixed points: block, beehive, loaf. Every live cell has ℓ ∈ {2,3}; every empty adjacent cell has ℓ ≠ 3. They are the automaton's stable memory bits.
• Oscillators — period-p cycles: the blinker (p = 2), pulsar (p = 3), and the pentadecathlon (p = 15). They function as clocks.
• Spaceships — patterns that translate across the grid: the glider (moves one cell diagonally every 4 generations, speed c/4), and the lightweight/middleweight/heavyweight spaceships (c/2 orthogonal). Here c is the speed of light — one cell per generation, the hard information-propagation limit since influence spreads at most one Moore-step per tick.
• Guns and puffers — the Gosper glider gun (Bill Gosper, 1970) emits a glider every 30 generations forever, disproving Conway's conjecture that no finite pattern grows without bound. Gliders are the signal wires; gun output is a clock signal; collisions between gliders act as logic gates.

Given these primitives, engineers wired up AND/OR/NOT gates, memory, and eventually a complete computer. That is the ladder from four rules to universal computation: still lifes store bits, oscillators tick, gliders carry signals, and controlled glider collisions compute.

The Naive Algorithm and Its Exact Cost

The textbook simulator scans a bounded W × H array, counts neighbors, and writes the next buffer. Let n = H rows, m = W columns.

next = new grid(H, W)          // second buffer
for r in 0..H-1:
  for c in 0..W-1:
    live = count8(cur, r, c)   // sum of 8 Moore neighbors
    if cur[r][c] == 1:
      next[r][c] = (live == 2 || live == 3) ? 1 : 0
    else:
      next[r][c] = (live == 3) ? 1 : 0
swap(cur, next)

Time: Θ(n·m) per generation — every cell is visited once and does O(1) work. Space: Θ(n·m) for the two buffers (double-buffering is mandatory). Over G generations the total is Θ(G·n·m).

Two standard speedups keep the same asymptotics but shrink the constant. First, maintain a rolling neighbor sum so count8 is O(1) amortized instead of re-summing 8 cells. Second, and far more important in practice, track only active cells: a cell can only change if it or a neighbor changed last generation. Keep a set of 'dirty' cells and their neighbors; each generation touches Θ(k) cells where k is the count of live cells plus their empty neighbors. For a lone glider on a million-by-million grid, the naive scan does 10¹² cell-visits per tick while the active-cell approach does ~15 — the difference between unusable and instant.

HashLife: Memoizing Spacetime Into Sub-Linear Time

The most beautiful algorithm in this space is HashLife, invented by Bill Gosper in 1984. It exploits the fact that real Life patterns are extraordinarily self-similar in space and periodic in time, and it attacks both at once.

The board is stored as a quadtree: a square of side 2ᵏ is a node with four children of side 2ᵏ⁻¹, down to single cells at k = 0. A canonical hash-consing table ensures every distinct subsquare is stored exactly once — two identical empty regions, or two identical gliders anywhere on the plane, share one physical node. The core trick: for a node of size 2ᵏ, HashLife computes the center 2ᵏ⁻¹ square advanced by 2ᵏ⁻² generations in one call, and memoizes the result keyed on the node's identity.

• Because nodes are deduplicated, a result computed for one glider is reused for every identical glider, everywhere, at every matching timescale.
• Because the jump doubles with depth, HashLife can leap 2⁶⁴ generations forward in a handful of table lookups once the cache is warm — a super-linear-in-time speedup, effectively O(log T) generations to advance T steps on regular patterns.

Complexity: time and space are both O(number of distinct quadtree nodes ever created); on highly regular patterns this is polylogarithmic in the pattern's size and near-constant in the time horizon. The trade-off: on chaotic, high-entropy patterns the cache-hit rate collapses, memory balloons, and HashLife loses to a plain bitwise scan. It is a memoization bet that pays off spectacularly when spacetime repeats and poorly when it does not.

Turing-Completeness and the Undecidability Wall

Life is Turing-complete: any computation a Turing machine can do, a Life pattern can do. The construction uses gliders as bits-in-flight, stable 'eaters' to consume unwanted output, glider guns as signal sources, and engineered collisions as logic gates; from NAND you get everything. Paul Rendell built a working Turing machine in Life; in 2010 he demonstrated a Universal Turing Machine, and the same lineage produced pattern-based implementations of memory, adders, and even a prime-number-printing 'primer'.

Turing-completeness has a sharp price. Because you can embed a UTM, the halting problem reduces to Life. Concretely, several natural questions about a starting configuration are undecidable — no algorithm decides them for all inputs:

• Will this pattern eventually reach the empty board (die out)?
• Will a given cell ever become alive?
• Does the population stay bounded forever?

The only fully general way to know a pattern's fate is to run it — and running it might never terminate. This is why no fast-forward algorithm, HashLife included, can be a genuine oracle: HashLife accelerates the simulation, but it cannot skip to an answer that is formally uncomputable. Emergence here is not a metaphor; it is a theorem about the irreducible gap between local rule and global outcome.

Edge Cases, Boundaries, and Common Failure Modes

Real implementations trip on the same handful of issues:

• In-place update (the classic bug): mutating cur while still reading it violates simultaneity. Always double-buffer, or update in a scan order that guarantees you never read a cell you already wrote — the former is safer.
• Boundary conditions: the true game is an infinite plane. A fixed W × H array must choose a policy: a toroidal wrap (edges connect, changing dynamics — a glider circles forever), a dead border (patterns silently die at the wall), or a dynamically growing grid. A glider fired at a dead edge that vanishes is not a bug in your rule — it is your boundary policy, and it will falsify any pattern that reaches the frame.
• Neighbor counting at corners: the count8 routine must clamp or wrap indices; off-by-one here corrupts exactly the boundary cells and is easy to miss on interior test patterns.
• Coordinate overflow: on an unbounded plane, gliders drift outward forever. Sparse and HashLife representations use arbitrary-precision or growable coordinates; a fixed int32 will eventually wrap.

Variants worth knowing: changing the rule string yields a whole family — HighLife (B36/S23) contains a natural self-replicator; Day & Night (B3678/S34678) is symmetric under state inversion; Seeds (B2/S) where every cell dies each generation. Move to a hex grid, add states, or go 3D and you leave Life but stay in the same undecidable, emergent universe of cellular automata.

Simulation strategies for the Game of Life: cost per generation and where each wins.

Algorithm	Time / generation	Space	Best regime
Naive full-grid scan	Θ(W·H)	Θ(W·H)	Small, dense, bounded grids
Sparse / active-cell list	Θ(k) where k = live+neighbors	Θ(k)	Sparse patterns, unbounded plane
Bitwise SIMD (word-parallel)	Θ(W·H / 64) wall-clock	Θ(W·H)	Dense grids, raw throughput
HashLife (Gosper, 1984)	amortized sub-linear per gen	O(distinct quadtree nodes)	Regular / periodic patterns, huge time-jumps