Conway's Game of Life

Conway's Game of Life is a two-dimensional cellular automaton invented by John Horton Conway in 1970. It is played on an infinite square grid consisting of cells with two possible states, alive or dead. Each cell has eight neighbors, namely the eight cells that touch it. There are four rules governing the evolution of patterns in the Game of Life.

- A live cell with fewer than two live neighbors dies (of loneliness) in the next generation.
- A live cell with more than three neighbors dies (of overcrowding) in the next generation.
- A live cell with two or three live neighbors survives (unchanged) in the next generation.
- A dead cell with three live neighbors becomes alive (gives birth) in the next generation.

There are several interesting types of patterns in the Game of Life.

**Still Lifes **

The simplest patterns are called still lifes because they don't change. Examples of still lifes include the block and tub, each consisting of four live cells, the boat, consisting of five live cells, and the beehive, ship, snake, and barge, each consisting of six live cells.

**Oscillators**

The next simplest type of pattern is an oscillator. This is a pattern which repeats after a finite number of generations, returning to its original configuration. Common period-2 oscillators include the blinker, beacon, toad, and clock. The pulsar is a common period-3 oscillator whose generations consist of 48, 56, and 72 live cells.

**Spaceships**

A spaceship is a pattern that moves, returning to the same configuration but shifted after a finite number of generations. The simplest spaceship is the glider, whose generations each consist of five live cells. The glider has period 4 and moves diagonally one cell every four generations (at one-quarter the speed of light). The next simplest spaceships are called lightweight, medium weight, and heavyweight spaceships. Each of them moves in a straight line at half the speed of light.

**Guns**

Guns are repeating patterns which produce a spaceship after a finite number of generations. The simplest gun, called the Gosper glider gun, produces a glider every 30 generations.

**Puffers**

Puffers are moving patterns which leave behind stable or oscillating debris at regular intervals.

**Rakes**

Rakes are moving patterns which leave behind spaceships at regular intervals.

**Breeders**

Breeders are complicated oscillating patterns which leave behind guns at regular intervals. Unlike guns, puffers, and rakes, each with a linear growth rate, breeders have a quadratic growth rate.

**Turing Machines **

A very interesting feature of the Game of Life is the existence of Turing machines, which can simulate computers. These amazing structures were conjectured by Conway in 1970, proved to exist by Conway, Berlekamp, and Guy in 1982, and finally constructed by Chapman in 2002. The initial generation of Chapman's Turing machine consists of 268,096 live cells and spans a region of 4558 by 21469 cells.