Conway's Game of Life

The Game of Life is a cellular automaton devised by the British mathematician John Horton Conway in 1970. It is the best-known example of a cellular automaton.

It made its first public appearance in the October 1970 issue of Scientific American, in Martin Gardner's "Mathematical Games" column. Ever since its publication, it has attracted much 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 Turing Machine: that is, anything that can be computed algorithmically can be computed within Conway's Game of Life.

Table of contents showTocToggle("show","hide")

1 Description

2 Examples of patterns

3 Variations on Life

4 External links

Description

The "game" is actually a zero-player game, meaning that its evolution is determined by its initial state, needing no input from human players. It runs on a grid of squares ("cells") which stretches to infinity in all directions. Each cell has eight "neighbours", which are the cells adjacent to it, including diagonally. Each cell can be in one of two states: it is either "alive" or "dead". (The terms "on" and "off" are also used.) The state of the grid evolves in discrete time steps. The states of all of the cells at one time are taken into account to calculate the states of the cells one time step later. All of the cells are then updated simultaneously.

The transitions depend only on the number of live neighbours:

A dead cell with exactly 3 live neighbours becomes alive (or is "born").
A live cell with 2 or 3 live neighbours stays alive; otherwise it dies (from "loneliness" or "overcrowding").

Examples of patterns

There are all sorts of different patterns that occur in the Game of Life, including static patterns ("still lifes"), repeating patterns ("oscillators" - a superset of still lifes), and patterns that translate themselves across the board ("spaceships"). The simplest examples of these three classes are shown below, with live cells shown in black, and dead cells shown in white.


Block	Boat	Blinker	Toad	Glider	LWSS

The "block" and "boat" are still lifes, the "blinker" and "toad" are oscillators, and the "glider" and "lightweight spaceship" ("LWSS") are spaceships.

Patterns can evolve for long periods before repeating. A "diehard" is a pattern that eventually disappears, but takes a long time. A "Methuselah" takes many steps before it stabilises as an oscillator plus spaceships. Of the following two patterns, the first is a diehard which takes 130 generations to vanish, and the second is a Methuselah which takes 5206 generations to generate 13 gliders then stabilise:

In the game's original appearance in "Mathematical Games", Conway offered a cash prize for any patterns that grew indefinitely. The first of these was found by Bill Gosper[?] in November 1970. 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.

The first glider gun found is still the smallest one known:

Gosper Glider Gun

Simpler patterns were later found that also have infinite growth. All three of the following patterns have infinite growth. The first has only 10 live cells (which is provably minimal). The second fits in a 5 x 5 square. The third is only 1 cell high:

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 further away. This "sliding block memory" can be used to simulate a counter. It is possible to construct logic gates AND, OR and NOT using gliders. It is possible to build a pattern which acts like a finite state machine connected to two counters. This has the same computational power as a Universal Turing Machine (see counter for the proof), so the Game of Life is as powerful as any computer with unlimited memory: it is Turing complete. Furthermore, a pattern can contain a collection of guns that combine 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.

Variations on Life

Since life's original inception, new rules have been developed. The standard Game of Life, in which a cell is "born" if it has exactly 3 neighbors, stays alive if it has 2 or 3 alive neighbors, and dies otherwise, is symbolized as "2/3". HighLife is therefore 23/36, because 6 neighbors causes a birth. HighLife is most well known for its replicators. Additional variations on life exist, although the vast majority of these universes are either too chaotic or desolate.

5678/35678 (chaotic) diamonds castrophes
/2 (exploding) phoenix, minimal
/234 (exploding) phoenix, lacey patterns
12345/3 (exploding) maze-like designs
125/36 (chaotic) Life-like 2x2 block rule
1357/1357 (exploding) everything is a replicator
1358/357 (chaotic) a balanced amoeba rule
23/3 (chaotic) "Conway's Life" (default)
23/36 (chaotic) "HighLife" (has replicator)
235678/3678 (stable) ink blot, quick drying
235678/378 (exploding) coagulations in chaos
238/357 (chaotic) broken life
245/368 (stable) death plus puffers and ships
34/34 (exploding) "34 Life"
34678/3678 (exploding) "Day Night"
45678/3 (exploding) slow coral growth
5/346 (stable) "Long life"

Source: Life32

External links

Life Lexicon (http://www.argentum.freeserve.co.uk/lex.htm)
Conway's Game of Life applet software home page (http://hensel.lifepatterns.net/)
"Eric Weisstein's Treasure Trove of the Life C.A. (http://www.ericweisstein.com/encyclopedias/life/)" - a site by Dr. Eric Weisstein[?] containing many descriptions and animations of Life patterns

Conway's Game of Life should not be confused with the board game "The Game of Life", for which see Hasbro's Game of Life.