Conway's Game of Life

Four rules, a grid of cells, and an entire universe of behaviour — including, hidden somewhere inside it, a working computer.

In 1970, the British mathematician John Conway sat down with a Go board and a handful of stones. He was hunting for the simplest possible cellular automaton — a grid of cells that evolve in lockstep according to a tiny rule — that nonetheless produced unpredictable, lifelike behaviour. Most candidate rules he tried collapsed within a few steps: either everything died, or everything filled the screen. After months of patient tuning, he found one that did neither.

That rule, published in Martin Gardner's column in Scientific American in October 1970, has been running, in one form or another, ever since.

Four rules

Picture an infinite chequerboard. Each cell is either alive (black) or dead (white). Time ticks forward in discrete generations. At each tick, every cell looks at its eight neighbours and updates itself, simultaneously, according to four rules:

1. A live cell with fewer than two live neighbours dies, as if from loneliness.
2. A live cell with two or three live neighbours survives to the next generation.
3. A live cell with more than three live neighbours dies, as if from overcrowding.
4. A dead cell with exactly three live neighbours becomes alive, as if by reproduction.

That is the entire game. There are no other rules. There is no player. You sketch a starting configuration, press go, and watch.

The remarkable thing — and the reason Conway spent months tuning the parameters — is that this rule sits on a knife edge. A slight nudge in either direction yields one of two boring fates: rapid extinction, or runaway combustion. At Conway's exact values, the long-term behaviour of an arbitrary starting pattern is, in general, impossible to predict by any means short of actually running it.

The zoo

Splatter a few hundred cells at random and run the simulation. After a few generations the chaos settles, and a small bestiary of recurring shapes precipitates out. A community of hobbyists has spent half a century cataloguing them.

There are still lifes — blocks, beehives, loaves — that, once formed, never change. There are oscillators — blinkers, toads, pulsars — that flicker between a small number of fixed states. And then there are spaceships: patterns that translate across the grid, walking forever in a fixed direction. The most famous of these is the glider, a five-cell shape that takes four generations to reproduce itself, shifted one square diagonally.

The glider's existence is a strange thing. The rules say nothing about gliders. They speak only of single cells deciding whether to live or die based on their immediate neighbours. Yet gliders are durable, countable objects with their own life cycle and direction of motion. They can be aimed. They can be collided. They can be used.

Enthusiasts have built glider guns — patterns that fire a glider every thirty generations forever, like a tap dripping particles. They have built reflectors, eaters, logic gates that take incoming gliders as input and output more gliders. A new kind of physics, with its own conservation laws and engineering tolerances, emerges on top of the original rule, talking about nothing the original rule mentions.

A computer made of cells

This raises an obvious question. If gliders are particles, and glider guns are emitters, and collisions are gates, can you build a computer out of them?

You can. In the year 2000, the hobbyist Paul Rendell did exactly that: he constructed, inside the Game of Life, a working Turing machine — tape, head, internal states — using nothing but Conway's four rules. A decade later, Adam Goucher built a fully programmable computer inside Life, sprawling across a grid of trillions of cells. It ran a program. Slowly. But it ran.

The implication is that the Game of Life is computationally universal: anything any computer can do, in principle Life can do as well, using only patterns of dots flickering on a grid. A chess engine. A weather model. A simulation of the Game of Life itself, running inside the Game of Life. Conway did not design any of this. He designed a rule. The computer is something the universe of that rule simply contains.

What it teaches

The Game of Life is not really about cellular automata. It is about a class of fact that is easy to state and very difficult to digest: a very simple rule can have effectively unlimited consequences, and there may be no shortcut to discovering what they are. You have to run it.

This is uncomfortable because most of how we do science assumes the opposite. We assume that simple rules permit short explanations — that if we understand the laws, we can in principle understand the consequences. The Game of Life is a counterexample sitting on the table. There is no compressed theory of which starting patterns produce gliders. The only way to find out is to look.

The Game of Life is a counterexample to the comfortable assumption that simple rules must permit short explanations.

Stephen Wolfram built an entire research programme — A New Kind of Science — around the suspicion that the real physics of our universe might be like this: a brutally simple rule, computationally irreducible, whose behaviour can only be unfolded one step at a time. Whether or not he is right, the suspicion is no longer a crazy one.

And it reframes the word in the title. A glider eats from the grid, holds together against perturbation, moves with purpose, and dies if disturbed badly enough. It is alive in every behavioural sense the word usually means, except that it is made of nothing but follow-the-rule. If a glider, why not a cell in your body? Why not, eventually, you?

Conway called it the Game of Life as a kind of joke. The joke has not aged well. The thing he named has turned out to be a small mirror held up to the way the universe seems to build complicated things out of simple ones — including, possibly, us.