Think Complexity

Chapter 7. Game of Life

One of the first cellular automata to be studied (and probably the most popular of all time) is a 2D CA called “The Game of Life,” or GoL for short. It was developed by John H. Conway and popularized in 1970 in Martin Gardner’s column in Scientific American. See http://en.wikipedia.org/wiki/Conway_Game_of_Life for more information.

The cells in GoL are arranged in a 2D grid, either infinite in both directions or wrapped around. A grid wrapped in both directions is called a torus because it is topographically equivalent to the surface of a doughnut; see http://en.wikipedia.org/wiki/Torus.

Each cell has two states (live and dead) and eight neighbors (north, south, east, west, and the four diagonals). This set of neighbors is sometimes called a Moore neighborhood.

The rules of GoL are totalistic, which means that the next state of a cell depends on the number of live neighbors only, not on their arrangement. The following table summarizes the rules:

Number of neighbors	Current state	Next state
2–3	live	live
0–1,4–8	live	dead
3	dead	live
0–2,4–8	dead	dead

This behavior is loosely analogous to real cell growth: cells that are isolated or overcrowded die, but at moderate densities they flourish.

GoL is popular for the following reasons:

• There are simple initial conditions that yield surprisingly complex behavior.

• There are many interesting stable patterns: some oscillate (with various periods), and some move like the spaceships in Wolfram’s Rule 110 CA.

• Like Rule 110, GoL is Turing complete. ...