Conway's Game of Life: Complexity from Simplicity

In 1970, mathematician John Horton Conway devised a cellular automaton so simple that its rules fit on an index card - yet so rich that it can simulate a universal Turing machine. The Game of Life, first introduced to the public through Martin Gardner's column in Scientific American [1], became one of the most studied objects in mathematics and computer science. It is not a game in the conventional sense: there are no players and no decisions. You set up an initial configuration of cells, press play, and watch what unfolds.

The Rules

The Game of Life takes place on an infinite two-dimensional grid. Each cell is either alive or dead. At each time step, every cell simultaneously updates according to four rules based on its eight neighbours (the Moore neighbourhood):

1. Underpopulation - A live cell with fewer than two live neighbours dies.
2. Survival - A live cell with two or three live neighbours survives.
3. Overpopulation - A live cell with more than three live neighbours dies.
4. Reproduction - A dead cell with exactly three live neighbours becomes alive.

That is it. No randomness, no external input, no exceptions. Every future state is entirely determined by the initial configuration. Yet from these four rules, an extraordinary zoo of behaviours emerges.

Still Lifes, Oscillators, and Spaceships

Patterns in the Game of Life fall into a natural taxonomy. Still lifes are stable configurations that do not change from one generation to the next - the block (a 2x2 square) and the beehive are common examples. Oscillators cycle through a fixed sequence of states: the blinker (period 2) and the pulsar (period 3) are well known. Spaceships are patterns that translate across the grid - the glider, discovered by Richard Guy, moves one cell diagonally every four generations and became the iconic symbol of the Game of Life [2].

The glider is worth tracing by hand, because it shows how motion appears in a system where nothing moves. Start with five live cells arranged like this, writing # for alive and . for dead:

gen 0       gen 1       gen 2       gen 3       gen 4    
. # . . .   . . . . .   . . . . .   . . . . .   . . . . .
. . # . .   # . # . .   . . # . .   . # . . .   . . # . .
# # # . .   . # # . .   # . # . .   . . # # .   . . . # .
. . . . .   . # . . .   . # # . .   . # # . .   . # # # .
. . . . .   . . . . .   . . . . .   . . . . .   . . . . .

No cell has changed position - cells cannot move, they can only be born or die. What has happened is that after four generations the same shape exists again, translated one square down and one square right. The glider is not an object; it is a pattern of births and deaths that happens to repeat itself in a new place. Every moving structure in Life works this way, which is why a "speed limit" exists at all: information can advance at most one cell per generation, because a cell's next state depends only on its immediate neighbours. That limit is universally called c, and the glider travels at c/4.

More complex patterns include guns - stationary patterns that periodically emit spaceships. Bill Gosper discovered the first glider gun in 1970, winning a $50 prize Conway had offered for a pattern proving unbounded growth. The existence of guns was the key to proving that the Game of Life can support unbounded growth and, ultimately, universal computation.

Von Neumann's Vision

The intellectual ancestry of the Game of Life traces back to John von Neumann, who in the 1940s sought to design a self-reproducing automaton. Working with Stanislaw Ulam, von Neumann developed the concept of cellular automata - lattices of identical finite-state machines that update synchronously based on local rules. Von Neumann's original construction used 29 states and was enormously complex [3]. Conway's contribution was to show that even a two-state automaton with a single, elegant rule set could produce behaviour of comparable richness.

Universality and Computation

Perhaps the most profound property of the Game of Life is that it is Turing-complete. Any computation that can be performed by a conventional computer can, in principle, be carried out by a sufficiently large Game of Life configuration. The claim sounds mystical until you see how the parts map over, at which point it becomes almost mundane.

A signal is a stream of gliders: glider present in a given time slot means 1, absent means 0. A clock is a glider gun, which emits at a fixed period and so supplies the regular timing every synchronous circuit needs. A logic gate is a carefully positioned collision - when two gliders meet, the outcome depends on their relative alignment and phase, and among the possible outcomes are annihilation (both vanish) and pass-through (both survive). A stream that annihilates an incoming stream is a NOT gate; arrange three streams so that one only survives when the other two are absent and you have NOR, from which every other gate can be built. Memory is a loop of gliders circulating between reflectors, and wires are simply the empty space the gliders cross.

Nothing in that list requires new rules. It is all the same four rules, arranged so that their side effects happen to implement Boolean algebra. Explicit constructions followed: a working Turing machine was built inside Life by Paul Rendell, and later a full universal constructor capable of building copies of itself - closing the loop back to von Neumann's original question.

Stephen Wolfram's systematic study of cellular automata in the 1980s placed the Game of Life within a broader classification framework, identifying it as a "Class IV" automaton - poised at the boundary between order and chaos, capable of supporting complex, long-lived transient structures [4].

Why It Matters for Biomimetics

The Game of Life is a paradigm example of emergence - complex global behaviour arising from simple local rules with no central coordination. This is exactly the principle underlying swarm intelligence, morphogenesis, and many other biological phenomena that biomimetics seeks to understand and replicate. Cells in the Game of Life have no awareness of the patterns they form, just as individual ants have no conception of the colony's logistics, and neurons have no knowledge of the thoughts they collectively produce.

The lesson is powerful: you do not need complex rules to produce complex behaviour. You do not need a central controller. You need only the right local interactions, applied consistently, and complexity emerges for free. This insight has influenced fields from artificial life to decentralised computing to self-organising materials.

Still a Live Research Object

It would be reasonable to assume that a 1970 toy has been fully explored. It has not, and the reason is instructive: the state space is astronomically large, the rules give no analytical handle on it, and so the only way forward is search. Distributed projects run soup searches, seeding enormous numbers of random starting grids and cataloguing whatever stabilises, which is how the census of known still lifes, oscillators and spaceships keeps growing.

Occasionally that search returns something people had wondered about for decades. For nearly fifty years every known spaceship travelled either orthogonally or diagonally; whether an oblique-moving "knightship" - one stepping like a chess knight - could exist at a small size was an open question. In 2018 a search program found one, now known as Sir Robin. There is no proof technique that would have produced it and no theory that predicted its shape. It was found by looking, which is a fair description of how most Life results have arrived.

You can explore the Game of Life yourself in the interactive simulation, where you can draw cells, choose classic patterns like the Gosper glider gun, and watch emergence happen in real time.