Conway’s Game of Life, the Universe, and Everything

by Jonathan Kujawa

John Conway invented the Game of Life in 1970, and it remains an active area of research and play fifty-six years later.

John Conway was a deeply original mathematician who made important contributions to multiple areas of mathematics. Indeed, when Dr. Conway passed away in 2020, I wrote an entire 3QD essay about his work and, as interesting as it is, the Game of Life (or GoL) didn’t make the cut.

The rules of GoL are deceptively simple. It is a zero-player game. This means that once the game starts, it runs on its own with no further player intervention. It is played on a very, very large grid of one-by-one squares that we will call “cells”[1]. Each cell can be “alive” or “dead”. In each turn of the game, an alive cell can remain alive, or die, and a dead cell can remain dead, or spring to life. In each turn of the game, whether a cell lives or dies depends solely on the state of its eight neighbors:

• a living cell with 2 or 3 living neighbors remains alive, and otherwise it dies [2];
• a dead cell with exactly 3 living neighbors springs to life, and otherwise it remains dead [3].

That’s it.

To play the game, in the zeroth turn you, as the creator deity, decide which cells are alive and which are dead. Thereafter, the game plays itself, turn-by-turn, and you watch your universe unfold:

As you can see from this example, strikingly complicated behaviors are unleashed by Conway’s two simple rules. Here, the starting configuration of roughly 100 cells at the top of the image emits a never-ending sequence of little creatures that wobble their way on a southeasterly heading. Those creatures are called “gliders”, and they continue wobbling away forever (they only appear to stop because the image cuts off).

Conway discussed the origins of GoL in an interview with the Numberphile folks. He described how he was originally motivated by John von Neumann’s work on self-replicating machines. However, von Neumann’s machines had 19 different possible states. No doubt with the aphorism “Make everything as simple as possible, but not simpler” in mind, Conway spent months tinkering with the GoL rules until he was down to two states and two rules.  Despite the simplicity, the game remained interesting.

By “interesting”, Conway meant unpredictable. This was Conway’s deep philosophical insight: saying GoL is unpredictable is to say that it is capable of anything, and if GoL is capable of anything, then it should be capable of everything [5]. That is, despite its simple algorithmic rules, GoL should be capable of arbitrary complexity. And indeed, in 1982, Conway proved that GoL is Turing-complete. Something is Turing-complete if it can simulate any Turing machine and, hence, can simulate any computer and perform any computation.

This means there is a starting configuration of GoL that, when the game runs, generates a list of all the prime numbers. And another configuration that computes the digits of pi. And another configuration that lets you play Doom, run ChatGPT, or do anything else you might want to do on a computer.

This is not just theoretical. A slightly mad group of people actually made a working game of Tetris that runs in Conway’s Game of Life. Instead of trying to one-shot their way from the simple tools of GoL to the complexity of Tetris, this group built it up through a sequence of intermediate steps.

First, they generalized GoL by using configurations known as OCTA megapixels. What is a megapixel? Imagine you would like a cell to evolve according to a rule that is different from Conway’s original rules. Since any Life-like rule is something that could be run on a computer, Conway’s GoL must be able to run your rule via some configuration in GoL. That is, it must be possible to create a virtual cell in GoL that evolves under your new rule.  A megapixel is exactly this: a 2,000 x 2,000 square of cells in Conway’s Game of Life in which, while the individual cells still evolve according to the original GoL rules, they collectively act like a single cell that evolves according to your new rule. Megapixels reverse Conway’s simplifying work in the Princeton math department tea room by adding back all the cell states and evolution rules that he stripped away, along with many, many more.

With megapixels in hand, the group built the various flavors of logic gates, used those gates to build a processor, developed a simple language called Cogol to run on that processor, and used Cogol to program Tetris on their virtual computer.

You read that right, and it’s absolutely bonkers: the group built a working virtual computer inside Conway’s Game of Life and programmed it to play Tetris! The group tackled the seemingly harder problem of building a programmable computer. But since we know how to program Tetris on a computer, that solved the problem. Their solution warms my mathematician’s heart. Mathematicians like to generalize problems, and we also like to solve new problems by reducing them to previously solved ones [6]. More recently, an enthusiast named blah built an entire 32-bit computer within GoL [7].

Let’s return to the OCTA megapixels for a moment. Megapixels can encode any Life-like rules. In particular, there is a megapixel that encodes the original two rules of Conway’s Game of Life. That means you can construct Conway’s Game of Life inside Conway’s Game of Life. There is a configuration of cells in GoL that, if you zoom out far enough, reveals megapixel cells that are themselves GoL cells. And those cells, in turn, can be configured so that if you zoom out even further, you find they are megapixels of GoL cells! Conversely, as far as you know, your original cells could have been megapixels built of even smaller cells that you would only see if you zoomed in.

Like the movie Inception, you can put Games of Life within Games of Life. Someone named saharan actually built this tower, and it’s quite fun (and a little disorienting) to zoom in, out, and around. You can find it here. One cool thing to note is that, as in Inception, time moves at different rates at the different scales. It takes thousands of game turns for one megapixel to decide whether to turn on or off. That is, one turn for a megapixel equals 1,000 turns for its constituent cells. And the same again if that megapixel is a cell in an even larger megapixel.

Being Turing-complete means that Conway’s Game of Life is infinitely rich. People continue to discover new things. For example, an oscillator is a configuration of cells that endlessly cycles through a fixed sequence of patterns. The pulsar on the right has period three because it repeatedly cycles through the same three shapes. Norton’s pinwheel from Conway’s notes up above is an oscillator with period four. It was a long-standing open question of whether every possible period actually occurred as the period of an oscillator in GoL. For example, is there an oscillator of period 629 in GoL? Yes! In 1996, David Buckingham proved that there exists an oscillator of every period 61 or greater by giving a general machine for constructing oscillators. Unfortunately — or maybe fortunately? — that machine doesn’t work to make oscillators with small periods, so those remained open for study. People worked their way through the small periods and found examples for most of them. Some examples were known early on, including ones found by David Buckingham when he was still in high school. Others proved elusive. It was only in 2023 that the final two periods, 19 and 41, were shown to exist by explicitly finding oscillators with those periods. You can read the research paper yourself, including a gallery of oscillators that you can click and run.

You can also ask questions about what could possibly appear as GoL runs. As we saw above, it is pretty easy to make a “glider gun” that generates gliders and shoots them wherever you like. Since gliders can readily be made, this leads to the question of what can be made from cleverly crashing gliders together. For example, a “still life’ is a configuration of cells that never changes. There are 1,646,147 such configurations with 23 living cells. Just a few months ago, it was proven that every single one of them can be made with gliders.

On the negative side, in 2022 Ilkka Törmä and Ville Salo found a still life and proved it cannot be created from something else. Specifically, they proved that if this still life existed at turn N of the game, then it must have been at that same spot on the game board at turn N-1, as well. Which means it was also there at turn N-2, N-3, … and so must have been there since the game began. In particular, it couldn’t have been created by gliders or anything else. Last year, 400spartans exhibited a still life with 154 cells that likewise cannot be created from anything else in GoL. But constructibility via gliders remains an open question for nearly all of the brobdignagian number of still life configurations with 24-153 cells.

If you’re interested in exploring for yourself, I highly recommend the community at ConwayLife.com. There you’ll find an active group discussing everything known and unknown about Conway’s Game of Life, and you can download Golly, a GoL player that can handle very large constructions. If you discover something new, you get to name it!

Or, if you just want to have fun making psychedelic images, you can play with this fantastic multi-colored version of Conway’s Game of Life.

 

 

[1] Or, if you like, a grid that is infinite in every direction. The point is that we don’t want to have to worry about reaching the edge while playing the game. Of course, you can have edges if you want but they will cause wonky behaviours. Alternatively, you could play GoL on a sphere, a doughnut, or some other shape.

[2] If you like, it dies from loneliness if it has only 0 or 1 living neighbors, and from overcrowding if it has 4+ neighbors.

[3] Unlike most forms of life on Earth, here you need three to create new life.

[4] Borrowed from Wikipedia.

[5] Life finds a way.

[6] There is a whole genre of science jokes whose punchline amounts to this.

[7] And the snake eats its tail when another user, Rei, built a computer-based emulator of blah’s GoL emulator of a computer.

Enjoying the content on 3QD? Help keep us going by donating now.