O'Reilly logo

Think Complexity by Allen B. Downey

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required