Computability Part 4: Conway's Game of Life

In the previous post we talked about tag systems. In this post (and the next one) we will cover cellular automata. The most famous cellular automata is Conway's Game of Life. Before providing the formal definitions, here is the Game of Life in action:

Formal definition:

A cellular automaton consists of a discrete n-dimensional lattice of cells, a set of states (for each cell), a notion of neighborhood for each cell, and a transition function mapping the neighborhood of each cell to a new cell state.

The system evolves over time, where at each step, the transformation function is applied over the lattice to determine the states of the next generation of cells.

Conway's Game of Life is a cellular automaton on a 2D plane with the following rules:

Any live cell with fewer than two live neighbors dies.

Any live cell with two or three live neighbors lives on to the next generation.

Any live cell with more than three live neighbors dies.

Any dead cell with exactly three live neighbors becomes a live cell.

In other words, a live cell stays alive during the next iteration if it has 2 or 3 live neighbors. A dead cell becomes live if it has exactly 3 live neighbors.

In the case of Conway's Game of Life, the lattice is a 2D grid, we have 2 states (on or off), the neighborhood of a cell consists of all adjacent cells (including corners), and the transition function is the one described above. Mathematician John Conway proposed the Game of Life in 1970.

The reason we started with Conway's Game of Life for discussing cellular automata is that this simple game with simple rules exhibits some very interesting behavior that has been classified for many years by people toying with the simulation.

First, we have still lives, patterns that don't change while stepping through the simulation. These patterns are stable: no cells die, no cells become live.

Next, we have oscillators, patterns that repeat with a certain periodicity:

In the above example, the last (bottom right) pattern has period 5 and is called Octagon 2. The other 3 patterns all have period 2.

More interestingly, we have spaceships - these are patterns that repeat but translate through space:

The above examples shows a couple of small spaceships, the tiny 5-cell glider and the lightweight spaceship or LWSS. There are many more spaceship patterns, some of them quite large (hundreds or even thousands of cells).

Most simulations tend to eventually stabilize into a combination of oscillators and still lives. Patterns that start from a small seed of a handful of cells and take a long time (in terms of iterations) to stabilize are called Methuselahs. Here is an example, nicknamed Acorn:

Conway conjectured that for any initial configuration, there is an upper limit of how many live cells can ever exist. This was proved wrong by the discovery of glider guns. A glider gun generates gliders every few iterations. The gliders continue moving away from the gun, thus running the simulation the number of live cells continues to grow.

One of the most popular glider guns is called Gosper glider gun, named after Mathematician and programmer Bill Gosper:

There are many other interesting patterns and constructions in the Game of Life discovered throughout the years. A few examples:

Eaters are still life or oscillator patterns that can interact and, over a number of iterations, absorb other patterns like spaceships, and return to their original state.
Reflectors are still life or oscillator patterns that can change the direction of incoming spaceships, and return to their original state.
Puffers are patterns that move like spaceships but leave behind a trail of patterns in their wake (unlike spaceships that cleanly translate).

There are many others, and combinations of them which give rise to interesting systems like circuits and logic gates based on spaceships and strategically placed still lives and oscillators.

Implementation

Let's look at a Python implementation for the Game of Life. We will use a wrap-around space, so we'll consider cells on the last column to be neighbors with cells on the first column and similarly cells on the last row to be neighbors with cells on the first row.

def make_matrix(width, height):
    return [[False] * width for _ in range(height)]

def neighbors(m, i, j):
    last_j = j + 1 if j + 1 < len(m[0]) else 0
    last_i = i + 1 if i + 1 < len(m) else 0

    return (m[i - 1][j - 1] + m[i - 1][j] + m[i - 1][last_j] +
        m[i][j - 1] + m[i][last_j] +
        m[last_i][j - 1] + m[last_i][j] + m[last_i][last_j])

def step(m1):
    m2 = make_matrix(len(m1[0]), len(m1))

    for i in range(len(m1)):
        for j in range(len(m1[0])):
            n = neighbors(m1, i, j)
            if n == 3:
                m2[i][j] = True
            elif n == 2 and m1[i][j]:
                m2[i][j] = True
    return m2

To run a simulation, we also need a function to print the game state and some initial conditions:

def print_matrix(m):
    for line in m:
        print(str.join('', ['#' if c else ' ' for c in line]))

m = make_matrix(10, 10)

m[0][1] = True
m[1][2] = True
m[2][0] = True
m[2][1] = True
m[2][2] = True

for _ in range(100):
    print_matrix(m)
    m = step(m)

Another very simple to implement system with powerful computational capabilities.

Turing completeness

It turns out the Game of Life is Turing complete, meaning it is also capable of universal computation. Gliders are key to this. In general, if the behavior of cells would be either repetitive (still life or oscillators cycle through 1 or more patterns) or chaotic, it would be hard to perform any computation. But gliders move and can interact with each other, thus enabling some non-chaotic processes.

We briefly discussed above how Game of Life patterns can be combined to form circuits that can process signals (in the form of spaceships) like logic gates and memory storage. Paul Rendell implemented a universal Turing machine in the Game of Life. His website (http://rendell-attic.org/gol/tm.htm) covers the details, which we won't go into due to the complexity. Suffice to say the patterns emerging in the Game of Life can be combined to build such a device. Paul also wrote a book about it¹.

We again encountered a system capable of computing anything computable, based only on a matrix of cells and a couple of rules (live cells with 2 or 3 neighbors stay alive, dead cells with exactly 3 neighbors become live).

The website https://conwaylife.com/ includes a lot of details on Conway's Game of Life, various patterns discovered, and a forum where people discuss their exploration of the system.

In the next post, we'll look at even simpler cellular automata: elementary cellular automata where cells have 2 possible states and 2 neighbors.

See Turing Machine Universality of the Game of Life. ↩