A board that plays itself
In 1970 the mathematician John Conway, at Cambridge, was looking for the simplest rule that would make a grid of cells do something interesting. He settled on one, and Martin Gardner described it in his column in Scientific American that October. It is called the Game of Life, though nobody plays it: you set up the board, and the rule does the rest.
The board is a grid of square cells. Each cell is either alive or dead, lit or dark. Time moves in generations. At each tick, every cell looks at its eight neighbours, the cells touching its sides and corners, and counts how many are alive. Then all the cells change at once:
- A dead cell with exactly 3 live neighbours is born.
- A live cell with 2 or 3 live neighbours survives.
- Every other cell is dead in the next generation, from loneliness with fewer than two neighbours or overcrowding with more than three.
That is the whole rule, usually written B3/S23: born with 3, survives with 2 or 3. Such a system, a grid of cells that all update together by the same local rule, is called a cellular automaton.
Try it: with Start on Random soup, watch the board for half a minute. The noisy patch breaks up, throws off a few small shapes that slide away across the board, and settles into scattered blocks and blinking lights. The display on the front of the board counts the generations and the live cells.
Every cell counts to eight
The rule never mentions shapes. It only says what one cell does with one number. The surprise is what that number does when every cell uses it at the same time.
Take three live cells in a row. The middle one has two live neighbours, so it survives. The two ends have one each, so they die. The cells directly above and below the middle each touch all three, so both are born. One generation later the row has become a column, and by the same counting it turns back into a row. This is the blinker, the smallest pattern that repeats.
The update has to be simultaneous. If cells changed one at a time, each would see a mixture of old and new neighbours, and the patterns would depend on the order in which the cells were visited.
Try it: step Show the rules to Neighbours. The clock slows to about one generation a second, the board magnifies its busiest stretch and every cell shows its count of live neighbours. A blue number is an empty cell about to be born, a white one a live cell that will survive and a red one a cell about to die. Watch the blue 3s light up at the next tick.
Still lifes, oscillators and spaceships
Leave a soup alone and most of what is left belongs to a few families. A still life never changes: the four-cell block and the six-cell beehive are the commonest, because every live cell has two or three neighbours and no empty cell has exactly three. An oscillator repeats in place after a fixed number of generations, its period: the blinker every 2, the large cross-shaped pulsar every 3 and the pentadecathlon every 15.
A spaceship repeats itself one step further on. The five-cell glider changes shape four times and ends up one cell further along a diagonal, so it crawls across the board at a quarter of a cell per generation. The lightweight spaceship moves twice as fast, straight along a row. Nothing in Life can move faster than one cell per generation, since a cell only ever feels its neighbours, and players call that speed c, the speed of light.
Try it: set Start to Pattern zoo and step Show the rules to Patterns. Still lifes turn green, oscillators amber and spaceships blue. The glider and the spaceship at the front fly off the board; everything else stays put.
Guns and endless growth
Conway guessed that no starting pattern could grow for ever: every one would die out, settle down or repeat. He offered 50 dollars to anyone who could prove him wrong. In November 1970 a group at MIT led by Bill Gosper did, with the glider gun: two shuttling shapes held between two blocks that rebuild themselves every 30 generations and fire off a new glider each time. The number of live cells grows without limit.
Some tiny patterns take a long time to settle. The R-pentomino is just five cells, yet on an endless grid it churns for 1,103 generations before it calms down, leaving 116 live cells, six of them gliders flying away.
Try it: set Start to Glider gun. A stream of gliders leaves the gun at the back left and marches towards the front right, one every 30 generations. At Patterns the gun turns violet; try Born with set to 3 or 6 and see whether it still works.
Change the rules
Life’s numbers are a careful balance. Make birth a little easier and the board fills with churning noise; make survival easier and live cells spread into a solid crust that never changes again; make it harder and everything dies. Life sits between freezing and boiling, where shapes can last long enough to travel and collide.
Other rules have their own characters. HighLife, B36/S23, behaves much like Life but adds a pattern that copies itself. Seeds, B2 with no survival at all, explodes from almost any start. Maze, B3/S12345, grows corridors. In the 1980s Stephen Wolfram sorted cellular automata into four rough classes: those that die out or go uniform, those that settle into still or repeating shapes, those that stay chaotic and those, like Life, that make long-lived structures that interact. Only the fourth class tends to produce anything you would want to name.
Try it: set Born with to 2 and the soup boils. Set it back to 3 (Life) and set Survives with to Always, and the live cells grow into a frozen crust. With Never every cell soon dies. The callout under the board says which of these the rule does to a random soup, and the chart beside the Scene plots the live cells generation by generation.
A computer made of gliders
A stream of gliders can carry a signal: a glider for a 1 and a gap for a 0. Two streams that cross can destroy each other, which is enough to build logic gates, and guns act as clocks. In 1982 Conway and his colleagues showed that Life can in principle compute anything a computer can: it is Turing-complete, the same power as the machines in Turing machines and computability. In 2000 Paul Rendell built a working Turing machine out of Life patterns, and in 2010 Andrew Wade found Gemini, a pattern that builds a copy of itself and destroys the original.
Being universal has a strange consequence. There is no general method that can look at a starting pattern and say whether it will ever die out, because that question is as hard as asking whether a program halts.
Cellular automata are older than Life. In the 1940s John von Neumann, prompted by Stanisław Ulam, designed a grid automaton with 29 states per cell that could copy itself, to show that a machine could reproduce. Simpler ones run on a single row of cells: Wolfram’s Rule 30 makes patterns random enough to be used as a source of random numbers, and Rule 110 was proved universal by Matthew Cook. The same idea, simple local rules producing order nobody planned, shows up in flocks of starlings, though birds steer smoothly through space instead of switching cells on and off.
What this model leaves out
- The board is finite. Life’s grid has no edges. This one shows 44 by 36 cells (fewer on a phone) and computes 32 more on every side out of view, where escaping gliders end in a little debris against a permanent dead border. Patterns that grow large, like the R-pentomino, can be changed by that border, so the board does not always end as an endless grid would.
- It starts again. Each start runs for a few hundred generations and then starts again from the same seed, so a gun’s stream of gliders stops growing on screen.
- Time is slowed. The board runs at eight generations a second, and at Neighbours at less than one, so you can follow each step. The tiles rise and sink to show a change; in the rule itself a cell simply switches. At Neighbours the plate magnifies part of the board, as a screen would; the frame and the camera stay put.
- The colours are an observer’s guess. At Patterns each group of cells within two of each other is compared with the board up to 30 generations earlier. Still lifes, oscillators and spaceships are labelled by what they did; a group that is crowded, collides or has a period longer than 30 is shown as not settled, and the gun is recognised only because the model placed it.
- Alive and dead are names. Nothing here is biology. The words are Conway’s metaphor for on and off, chosen because the patterns seem to grow, move and die.