abyiber.com
Back to Blog

Conway's Game of Life: Complexity from Simplicity

How four simple rules on a grid produce gliders, oscillators, and Turing-complete computation, launching the field of artificial life.

2025-09-15
Share
Artificial Lifecellular-automataconways-game-of-lifeemergence

Terminology

Term Definition
Cellular Automaton A discrete model consisting of a grid of cells, each in a finite state, updated simultaneously according to local rules based on neighbor states
Moore Neighborhood The 8 cells surrounding a given cell in a 2D grid (horizontally, vertically, and diagonally adjacent)
Still Life A pattern in the Game of Life that remains unchanged from one generation to the next
Oscillator A pattern that returns to its initial state after a fixed number of generations (its period)
Glider A small pattern that translates itself across the grid over successive generations
Emergence Complex global behavior arising from simple local interactions, where the whole exhibits properties not present in any individual part Turing Complete A system capable of simulating any Turing machine, meaning it can compute anything that is computable given enough time and space Generation One discrete time step in a cellular automaton where all cells update simultaneously according to the rules Garden of Eden A configuration that cannot arise from any predecessor state, meaning it can only exist as an initial condition

What & Why

In 1970, mathematician John Conway devised a zero-player game on an infinite 2D grid. Each cell is either alive or dead, and four rules govern what happens at each tick:

  1. A live cell with fewer than 2 live neighbors dies (underpopulation).
  2. A live cell with 2 or 3 live neighbors survives.
  3. A live cell with more than 3 live neighbors dies (overpopulation).
  4. A dead cell with exactly 3 live neighbors becomes alive (reproduction).

That is the entire specification. No randomness, no external input, no player decisions. Yet from these four rules, staggering complexity emerges: self-replicating patterns, logic gates, clocks, and even a full computer have been built inside Life.

The Game of Life matters because it is the canonical example of emergence. It demonstrates that you do not need complicated rules to produce complicated behavior. This insight underpins artificial life research, complex systems science, and even philosophical arguments about whether simple physical laws can give rise to consciousness.

How It Works

The Update Rule

Every cell examines its Moore neighborhood (8 surrounding cells), counts the number of live neighbors k, and applies the birth/survival rule. The standard shorthand is B3/S23: birth on exactly 3, survival on 2 or 3.

? Center cell: alive, k=3, survives Live = filled Dead = dark Yellow border = focus

Common Patterns

Still lifes are stable: every live cell has 2 or 3 neighbors, and no dead cell has exactly 3. The Block (2x2 square) and Beehive are the simplest examples.

Oscillators cycle through a fixed sequence of states. The Blinker (period 2) flips between a horizontal and vertical line of three cells.

Spaceships translate across the grid. The Glider moves one cell diagonally every 4 generations, making it the simplest spaceship.

Turing Completeness

Life is Turing complete. By arranging glider streams as signal carriers and constructing collision-based logic gates (AND, OR, NOT), you can build arbitrary circuits. A glider gun (like the Gosper Glider Gun) produces a steady stream of gliders, acting as a clock signal. This means any computable function can, in principle, be evaluated inside the Game of Life.

Complexity Analysis

For an $N \times N$ grid simulated for $T$ generations:

Approach Time per Generation Space Notes
Naive grid scan $O(N^2)$ $O(N^2)$ Check every cell, count 8 neighbors
Sparse set (only live cells) $O(L)$ where $L$ = live cells $O(L)$ Hash set of coordinates, iterate live + neighbors
HashLife (memoized) $O(L)$ amortized, exponential time skips $O(L \log L)$ Quadtree + memoization, can skip $2^k$ generations

The naive approach processes all $N^2$ cells regardless of how many are alive. The sparse approach only visits live cells and their neighbors, giving a speedup proportional to the fraction of the grid that is active. HashLife, invented by Bill Gosper, exploits the fact that many sub-patterns repeat across space and time, caching results in a quadtree to skip exponentially many generations at once.

Total simulation cost for $T$ generations on the naive grid:

$O(T \cdot N^2)$

Implementation

ALGORITHM SimulateLife(grid, rows, cols)
INPUT: grid: 2D boolean array [rows x cols], rows: integer, cols: integer
OUTPUT: next: 2D boolean array [rows x cols] (the next generation)

BEGIN
  next <- CREATE 2D boolean array [rows x cols], all FALSE

  FOR r FROM 0 TO rows - 1 DO
    FOR c FROM 0 TO cols - 1 DO
      k <- 0
      FOR dr FROM -1 TO 1 DO
        FOR dc FROM -1 TO 1 DO
          IF dr = 0 AND dc = 0 THEN CONTINUE
          nr <- r + dr
          nc <- c + dc
          IF nr >= 0 AND nr < rows AND nc >= 0 AND nc < cols THEN
            IF grid[nr][nc] = TRUE THEN
              k <- k + 1
            END IF
          END IF
        END FOR
      END FOR

      IF grid[r][c] = TRUE THEN
        IF k = 2 OR k = 3 THEN
          next[r][c] <- TRUE
        END IF
      ELSE
        IF k = 3 THEN
          next[r][c] <- TRUE
        END IF
      END IF
    END FOR
  END FOR

  RETURN next
END

ALGORITHM SimulateLifeSparse(liveCells)
INPUT: liveCells: set of (row, col) pairs
OUTPUT: nextLive: set of (row, col) pairs (the next generation)

BEGIN
  neighborCount <- EMPTY MAP of (row, col) -> integer

  FOR EACH (r, c) IN liveCells DO
    FOR dr FROM -1 TO 1 DO
      FOR dc FROM -1 TO 1 DO
        IF dr = 0 AND dc = 0 THEN CONTINUE
        key <- (r + dr, c + dc)
        neighborCount[key] <- neighborCount[key] + 1
      END FOR
    END FOR
  END FOR

  nextLive <- EMPTY SET

  FOR EACH (cell, count) IN neighborCount DO
    IF count = 3 THEN
      ADD cell TO nextLive
    ELSE IF count = 2 AND cell IN liveCells THEN
      ADD cell TO nextLive
    END IF
  END FOR

  RETURN nextLive
END

Real-World Applications

  • Theoretical computer science: Life is a concrete proof that simple local rules can yield universal computation, informing research on the minimal requirements for Turing completeness
  • Biological modeling: Cellular automata model tumor growth, tissue development, and population dynamics where local cell interactions drive global patterns
  • Cryptography and random number generation: Certain CA rules produce pseudo-random sequences used in stream ciphers and PRNG designs
  • Urban planning and traffic simulation: Grid-based CA models simulate traffic flow (Nagel-Schreckenberg model) and urban sprawl
  • Art and generative design: Life-like rules power procedural content generation in games, music, and visual art installations
  • Self-replicating machines: Von Neumann's original cellular automaton concept (which Life simplifies) laid the groundwork for studying self-replication in engineering and nanotechnology

Key Takeaways

  • The Game of Life uses just four rules on a 2D grid, yet produces gliders, oscillators, guns, and even full computers
  • It is the textbook example of emergence: complex global behavior from simple local interactions
  • Life is Turing complete, proven by constructing logic gates from glider collisions
  • Naive simulation costs $O(N^2)$ per generation; sparse and memoized approaches (HashLife) dramatically reduce this for typical patterns
  • Cellular automata inspired by Life are used in biology, cryptography, traffic modeling, and generative art