How does it work?
John Conway's Game of Life (1970)
The board is a grid of cells. Each one is alive or dead and has 8 neighbors (diagonals included). In every generation all cells at once count their live neighbors N and apply a single rule:
The B/S notation (born / survive) lists the neighbor counts at which a cell is born and at which it survives. Conway's game is B3/S23; change the digits and you get other worlds: HighLife, Seeds, Day & Night, Maze.
Emergence: more than the sum of its parts
Nobody programmed the glider. The rule only talks about a single cell and its neighbors, and yet “objects” appear that move, collide, multiply and die. This rise of complex behavior from simple rules is called emergence. In the same way, simple interactions give rise to schools of fish, traffic jams and patterns on seashells.
A computer built from gliders
The Gosper glider gun fires a glider every 30 generations — a stream of bits: a glider means 1, a gap means 0. Where two streams cross, suitably placed gliders annihilate on collision, so guns and collisions act as logic gates NOT, AND and OR. Gates plus memory can make any computer, which is why the Game of Life is Turing complete: it can compute anything that can be computed. Berlekamp, Conway and Guy sketched the construction in the book Winning Ways (1982), and in 2000 Paul Rendell built a working Turing machine inside the game.
Cellular automata
In general, a cellular automaton is a grid of cells, a finite number of states and one local rule applied everywhere at the same time. The idea comes from John von Neumann and Stanisław Ulam — a mathematician from Lwów (now Lviv) — in the 1940s. Today automata are used to model forest fires, crystallization, traffic and tissue growth.
One-dimensional automata (Wolfram)
The cells sit in a single row, and we draw each new generation below the previous one — the picture shows time passing. The new state depends on a cell and its two neighbors: that's 2³ = 8 possible neighborhoods, and each can give 0 or 1, so there are 2⁸ = 256 rules. Stephen Wolfram numbered them in 1983: read the results for neighborhoods 111, 110, …, 000 as a binary number.
Rule 90 is simply sit+1 = si−1 ⊕ si+1 (exclusive or). Starting from a single cell, row t gives the binomial coefficients (t⁄k) mod 2 — Pascal's triangle with only the odd numbers kept. The result is the Sierpiński triangle, a fractal. You'll find more fractals in the Fractal experiment.
Rule 30 grows chaos from a single cell, so unpredictable that its center column has been used as a random number generator. Rule 110 is Turing complete — Matthew Cook proved it (published in 2004). Rule 184 models traffic: the ones are cars that move right when the square ahead is free; their number never changes.
Langton's ant (1986)
Chris Langton invented an “ant” on a grid. On an empty square it turns 90° right, on a filled one — left; it flips the square and steps forward. For the first ~10,000 steps it scribbles a chaotic blob, and then it suddenly starts building a highway: it repeats the same sequence of 104 steps, which shifts it 2 squares diagonally — forever.
Nobody has proved that the highway appears for every starting arrangement of squares — it's still an open problem. All we know is that the ant never stays in a bounded region forever (the Bunimovich–Troubetzkoy theorem).
Simplifications: the boards are finite and their edges are glued into a torus (384 × 384 cells in the Game of Life, 320 × 320 for the ant), and the 1D automaton's row is a ring. Real automata live on an infinite plane — here a glider that flies off one edge comes back from the other side and may hit whatever it left behind. The numbers in the pattern descriptions (e.g. 1103 generations of the R-pentomino) refer to an infinite plane.