Conway’s Game of Life

Overview

Conway’s Game of Life is a well-known simple cellular automaton. Its behavior is quite straightforward:

• The lattice is an infinite grid of black and white cells.
• The state of each cell is whether the color of the cell is black or white (also commonly referred to as “dead” or “alive”, respectively).
• The neighborhood of the cell is the eight cells around it.
• The transition function is based on a few constraints:

Survival: If the cell is alive and two or three of its neighbors are alive, the cell remains alive

Birth: If the cell is dead and exactly three of its neighbors are alive, the cell becomes alive

Death: If the cell is alive and fewer than two or more than three of its neighbors are alive, the cell dies

Patterns and Properties

From these rules come a large number of patterns common to the game. These patterns include

• Oscillators : a group of cells that periodically repeat patterns in place

• Gliders : small clusters of cells that travel across the lattice

• Glider Guns : structures that produce a steady stream of gliders

Small structures can be combined to form larger and more computationally interesting structures. The most obvious example of this is the creation of logic gates. Below we can see examples of an AND, OR, and NOT gate, respectively.

This is incredibly significant – knowing that we can create any logic function using the Game of Life leads us to the conclusion that we could create full computers using only the Game of Life as a platform. In fact, this has been proven. Conway and a few others proved shortly after the creation of the Game of Life that it is Turing-complete and can theoretically be used to compute anything that is computable. The first Game of Life Turing machine was created by Paul Rendell and can duplicate a pattern of ones that it is fed.

Further work has even shown that full CPUs can be constructed entirely using the Game of Life.