Skip to Main Content
Think Complexity
book

Think Complexity

by Allen B. Downey
March 2012
Beginner content levelBeginner
160 pages
4h 6m
English
O'Reilly Media, Inc.
Content preview from 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 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. ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Unikernels

Unikernels

Russell Pavlicek
Elemental Design Patterns

Elemental Design Patterns

Jason McColm Smith
LEGO® with Dad

LEGO® with Dad

Warren Nash

Publisher Resources

ISBN: 9781449331672Errata