The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, alive or dead. Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:
The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed — births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick (in other words, each generation is a pure function of the preceding one). The rules continue to be applied repeatedly to create further generations.
Conway chose his rules carefully, after considerable experimentation, to meet these criteria:
John Horton Conway FRS (born 26th December 1937) is a British mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory. He has also contributed to many branches of recreational mathematics, notably the invention of the cellular automaton called the Game of Life. Conway is currently Professor of Mathematics and John Von Neumann Professor in Applied and Computational Mathematics at Princeton University. He is also currently a visiting professor at the City University of New ork’'s Queens College.
...You get surreal numbers by playing games. I used to feel guilty in Cambridge that I spent all day playing games, while I was supposed to be doing mathematics. Then, when I discovered surreal numbers, I realized that playing games IS mathematics – John Horton Conway.
See John Horton Conway: the world’s most charismatic mathematician.
The Gosper glider gun (the animation above) produces its first glider on the 15th generation, and another glider every 30th generation from then on. This first glider gun is still the smallest one known.
It is possible for gliders to interact with other objects in interesting ways. For example, if two gliders are shot at a block in just the right way, the block will move closer to the source of the gliders. If three gliders are shot in just the right way, the block will move farther away. This “sliding block memory” can be used to simulate a counter. It is possible to construct logic gates such as AND, OR and NOT using gliders. It is possible to build a pattern that acts like a finite state machine connected to two counters. This has the same computational power as a universal Turing machine, so the Game of Life is theoretically as powerful as any computer with unlimited memory and no time constraints: it is Turing complete.
Animated Glider
Animated Lightweight Spaceship
Furthermore, a pattern can contain a collection of guns that fire gliders in such a way as to construct new objects, including copies of the original pattern. A universal constructor can be built which contains a Turing complete computer, and which can build many types of complex objects, including more copies of itself. Stable Conway’s Game of Life puffer pattern running for 1939 generations.
Below: Glider gun pattern with toroidal array (top-bottom edge wrap around)
The “game” is a zero-player game, meaning that its evolution is determined by its initial state, requiring no further input. One interacts with the Game of Life by creating an initial configuration and observing how it evolves.
These are completely stable (Block, Beehive, Loaf, Boat, and 19x19 and 20x20 maximum-density still life); each generation is identical to the previous.
The pulsar (the first) is the most common period-3 oscillator. The great majority of naturally occurring oscillators are period-2, like the beacon, blinker and the toad (the other three shown here), but periods 4, 8, 14, 15, 30 and a few others have been seen on rare occasions.
Patterns called Methuselahs can evolve for long periods before stabilizing, the first-discovered of which was the F-pentomino (first). Diehard is a pattern that eventually disappears (rather than merely stabilizes) after 130 generations, which is conjectured to be maximal for patterns with seven or fewer cells (second). Acorn takes 5206 generations to generate 633 cells including 13 escaped gliders (third).
A gun is a configuration that repeatedly shoots out moving objects such as the glider. A puffer train is a configuration that moves but leaves behind a trail of persistent ‘smoke’. (See the top of this section.)
Smaller patterns were later found that also exhibit infinite growth. All three of the subsequent patterns below grow indefinitely: the first two create one “block-laying switch engine” each, while the third creates two. The first has only 10 live cells (which has been proven to be minimal). The second fits in a 5 × 5 square. The third is only one cell high.
Later discoveries included other “guns”, which are stationary, and which shoot out gliders or other spaceships; “puffers”, which move along leaving behind a trail of debris; and “rakes”, which move and emit spaceships.
