Conway's Game of Life

John Horton Conway's Game of Life is a cellular automaton running on a grid, where each cell can be either "alive" or "dead". The transitions depend only on the number of live neighbors (out of the 8 immediate neighbors of each cell):

A dead cell with exactly three live neighbors becomes alive.

A live cell with fewer than two live neighbors dies.

A live cell with more than three live neighbors dies.

The game of life was invented in 1970 (which day?). It has spurred a lot of interest because of the surprising ways the patterns can evolve. From a theoretical point of view it is interesting because it has the power of a universal computer, that is, anything that can be computed algorithmically can be done so within the game of life.

There are all sorts of different patterns that occur in the game of life, including static patterns (still lifes), repeating patterns (oscillators), and patterns that translate themselves across the board. The most common of these three classes are shown below.

XXX

 XX         XXX        X

 XX                     X

Block     Blinker     Glider

In the game's original appearance in Mathematical Recreations, Conway offered a cash prize for any patterns that grew indefinitely. The first of these were found by Gosper. They include guns, which shoot out gliders or other spaceships, puffers, which move along leaving behind a trail of debris, and rakes, which do both. He also discovered a pattern with a quadratic growth rate, called a breeder, which works by leaving behind a trail of guns. Since then various complicated constructions have been made, including glider logic gates, an adder, a prime number generator, and a unit cell which emulates the game of life at a much larger scale and slower pace.

External link:

Life Lexicon

/Talk