Conway's Game of Life: Four Rules, One Universal Computer

Four rules, no exceptions

Conway's Game of Life is a cellular automaton on an infinite square grid. Each cell is either alive or dead, and every cell looks at its eight neighbours (the Moore neighbourhood) to decide what it becomes in the next generation. The entire physics of this universe is four lines:

live cell with 2 or 3 live neighbours  → survives
live cell with < 2 live neighbours      → dies (underpopulation)
live cell with > 3 live neighbours      → dies (overcrowding)
dead cell with exactly 3 live neighbours → becomes alive (birth)

In the standard notation this is B3/S23: born on 3 neighbours, survives on 2 or 3. Crucially, all cells are updated simultaneously from the same snapshot. Update a cell in place and you are no longer running Life — you are running a different, direction-biased automaton. Every correct implementation therefore keeps two buffers and swaps them.

Conway published the rules in 1970, after searching for a rule set that was neither doomed to die out nor prone to exploding without limit. B3/S23 sits exactly on that edge: from a random soup, roughly 3% of cells stay alive forever, most of the activity settles into small stable debris, and a rare few structures keep moving.

The zoo: still lifes, oscillators, spaceships

After a few hundred generations a random soup decomposes into a handful of recurring shapes. Still lifes never change: the block (2×2), the beehive, the loaf, the boat. Oscillators return to their initial state after a fixed period: the blinker (period 2), the toad (period 2), the beacon (period 2), the pulsar (period 3), the pentadecathlon (period 15).

The famous one is the glider — five cells that reproduce themselves one cell diagonally every four generations, so they travel at c/4, where c is one cell per generation (the maximum information speed on the grid). The lightweight spaceship and its heavier cousins travel orthogonally at c/2. The glider matters because it is a moving, countable unit of information: a glider stream is a wire.

. O .        glider, generation 0
. . O
O O O

Then there are guns. Bill Gosper's glider gun (1970) is a period-30 oscillator that emits a glider every 30 generations forever — the first known pattern with unbounded growth, and the reason the Game of Life is not just decoration.

Why it is Turing-complete

With gliders as signals and still lifes as walls, you can build logic. A glider stream is a stream of bits — a glider present in a slot means 1, absent means 0. Two glider streams crossing at the right angle annihilate, which gives you a NOT gate against a reference stream from a gun; guns, eaters (still lifes that absorb an incoming glider and recover) and reflectors give you AND, OR and fan-out. Once you have a universal gate set plus a way to route and delay signals, you have combinational logic; add a loop of gliders as memory and you have sequential logic.

That is enough for a universal Turing machine, so Life is Turing-complete: any computation any computer can do, this grid can do. People have built binary counters, a working Turing machine, a pattern that prints the primes, and even a version of Life running inside Life. The practical consequence is sobering — no shortcut can tell you in general whether a given pattern eventually dies out. That question is equivalent to the halting problem, and therefore undecidable.

Implementing it fast

The naive version is two nested loops and eight neighbour reads per cell: O(w·h) per generation with a large constant. It is fine for a 300×200 canvas at 60 fps, and that is exactly what the simulation on this site does — one Uint8Array for the current generation, one for the next, swapped each step:

for (let y = 0; y < h; y++) {
  for (let x = 0; x < w; x++) {
    const i = y * w + x;
    let n = 0;
    for (let dy = -1; dy <= 1; dy++)
      for (let dx = -1; dx <= 1; dx++) {
        if (dx === 0 && dy === 0) continue;
        // wrap-around torus keeps the branchless inner loop
        const yy = (y + dy + h) % h, xx = (x + dx + w) % w;
        n += cur[yy * w + xx];
      }
    next[i] = n === 3 || (n === 2 && cur[i]) ? 1 : 0;
  }
}
[cur, next] = [next, cur];   // never update in place

Two easy accelerations. First, bit-parallel evaluation: pack 32 or 64 cells into one integer, and compute the neighbour sum of a whole word at once with shifts and a small chain of half-adders. A well-known trick sums the three horizontal neighbours per row into two bitplanes and then combines the three rows, evaluating B3/S23 for 64 cells with about twenty bitwise operations — a 20–50× win over per-cell arithmetic, with the exact factor depending on the CPU and the pattern.

Second, skip the empty space. Most of a large board is quiescent, so track which tiles changed last generation and only re-evaluate those tiles and their immediate neighbours. This alone makes million-cell boards interactive.

HashLife, and the pattern that runs faster the longer it runs

Bill Gosper's HashLife (1984) is a different idea entirely. It stores the board as a quadtree: a node of size 2ⁿ is four children of size 2ⁿ⁻¹. Nodes are hash-consed — identical subtrees are stored exactly once — and for each node the algorithm memoises the result of advancing its centre by 2ⁿ⁻² generations.

Because Life is deterministic and local, that memo is reusable everywhere the same subpattern appears, and in space and time: a period-30 gun repeats, a still life repeats, empty space repeats. Cache hits let HashLife jump forward in enormous strides, and its running time is measured in cache lookups rather than cells. Highly regular patterns can be advanced by 2⁶⁴ generations in seconds — something no per-cell loop can approach. The trade-offs are real, though: the memo table grows without bound (it must be garbage-collected), you cannot cheaply observe every intermediate generation, and on chaotic, non-repeating soup the cache barely hits and HashLife is slower than a tight bit-parallel loop. Interactive canvases like the one on this page therefore stay with the bitboard approach.

Frequently asked questions

Try it live

Everything above runs in your browser — open Game of Life and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.