Conway Wrote a Four-Rule "Game" in 1970 That Turned Out to Compute Anything

John Horton Conway was a young mathematician at Gonville and Caius College, Cambridge, in 1970 when he was looking for a simple set of cellular-automaton rules that would generate complex behavior without descending into the trivial — patterns either dying out, freezing, or expanding boringly forever. He sketched candidate rule sets at his kitchen table, played them out on graph paper with poker chips, and, after several months of trial and error, settled on four rules:

A live cell with fewer than two live neighbors dies. A live cell with two or three lives. A live cell with more than three dies. A dead cell with exactly three live neighbors becomes alive. That's the entire game. Conway described it to Martin Gardner, the Mathematical Games columnist for Scientific American. Gardner ran it in the October 1970 issue under the title "The fantastic combinations of John Conway's new solitaire game 'life.'"

The response was immediate and obsessive. Conway had also offered $50 to anyone who could prove that some Life pattern grew without bound. Two weeks later, an MIT student team led by Bill Gosper produced the glider gun — a small static configuration that periodically emits a small mobile pattern called a glider, indefinitely. That implied unbounded growth and won the prize. The deeper consequence took a few more years to articulate. Because gliders can be combined to form logic gates and gates can be combined to form a universal Turing machine, Conway's Game of Life is computationally as powerful as any programmable computer. Anything any computer can compute, you can compute by drawing the right initial configuration in pencil on graph paper and applying four rules, repeatedly, by hand.