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

Start Free Trial

No credit card required