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 neighborsCurrent stateNext state
2–3livelive
0–1,4–8livedead
3deadlive
0–2,4–8deaddead

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. ...

Get Think Complexity now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.