This HTML version of Think Complexity, 2nd Edition is provided for convenience, but it is not the best format of the book. In particular, some of the symbols are not rendered correctly.
You might prefer to read the PDF version.
Chapter 6 Game of Life
In this chapter we consider two-dimensional cellular automatons, especially John Conway’s Game of Life (GoL). Like some of the 1-D CAs in the previous chapter, GoL follows simple rules and produces surprisingly complicated behavior. And like Wolfram’s Rule 110, GoL turns out to be universal; that is, it can compute any computable function, at least in theory.
Complex behavior in GoL raises issues in the philosophy of science, particularly related to scientific realism and instrumentalism. I discuss these issues and suggest additional reading.
At the end of the chapter, I demonstrate ways to implement GoL efficiently in Python.
The code for this chapter is in chap06.ipynb in the repository for this book. More information about working with the code is in Section ??.
6.1 Conway’s GoL
One of the first cellular automatons to be studied, and probably the most popular of all time, is a 2-D 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.
The cells in GoL are arranged in a 2-D 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 8 neighbors—north, south, east, west, and the four diagonals. This set of neighbors is sometimes called a “Moore neighborhood”.
Like the 1-D CAs in the previous chapters, the Game of Life evolves over time according to rules, which are like simple laws of physics.
In GoL, the next state of each cell depends on its current state and its number of live neighbors. If a cell is alive, it survives if it has 2 or 3 neighbors and dies otherwise. If a cell is dead, it stays dead unless it has exactly 3 neighbors.
The following table summarizes the rules:
This behavior is loosely analogous to real cell growth: cells that are isolated or overcrowded die; at moderate densities they flourish.
GoL is popular because:
6.2 Life patterns
If you run GoL from a random starting state, a number of stable patterns are likely to appear. Over time, people have identified these patterns and given them names.
For example, Figure ?? shows a stable pattern called a “beehive”. Every cell in the beehive has 2 or 3 neighbors, so they all survive, and none of the dead cells adjacent to the beehive has 3 neighbors, so no new cells are born.
Other patterns “oscillate”; that is, they change over time but eventually return to their starting configuration (provided they don’t collide with another pattern). For example, Figure ?? shows a pattern called a “toad”, which is an oscillator that alternates between two states. The “period” of this oscillator is 2.
Finally, some patterns oscillate and return to the starting configuration, but shifted in space. Because these patterns seem to move, they are called “spaceships”.
Figure ?? shows a spaceship called a “glider”. After a period of 4 steps, the glider is back in the starting configuration, shifted one unit down and to the right.
Depending on the starting orientation, gliders can move along any of the four diagonals. There are other spaceships that move horizontally and vertically.
People have spent embarrassing amounts of time finding and naming these patterns. If you search the web, you will find many collections.
6.3 Conway’s conjecture
From most initial conditions, GoL quickly reaches a stable state where the number of live cells is nearly constant (possibly with some oscillation).
But there are a some simple starting conditions that take a long time to settle down and yield a surprising number of live cells. These patterns are called “Methuselahs” because they are so long-lived.
One of the simplest is the r-pentomino, which has only five cells, roughly in the shape of the letter “r”. Figure ?? shows the initial configuration of the r-pentomino and the final configuration after 1103 steps.
This configuration is “final” in the sense that all remaining patterns are either stable, oscillators, or gliders that will never collide with another pattern. In total, the r-pentomino yields 6 gliders, 8 blocks, 4 blinkers, 4 beehives, 1 boat, 1 ship, and 1 loaf.
The existence of long-lived patterns prompted Conway to wonder if there are initial patterns that never stabilize. He conjectured that there were not, but he described two kinds of pattern that would prove him wrong, a “gun” and a “puffer train”. A gun is a stable pattern that periodically produces a spaceship—as the stream of spaceships moves out from the source, the number of live cells grows indefinitely. A puffer train is a translating pattern that leaves live cells in its wake.
It turns out that both of these patterns exist. A team led by Bill Gosper discovered the first, a glider gun now called Gosper’s Gun, which is shown in Figure ??. Gosper also discovered the first puffer train.
There are many patterns of both types, but they are not easy to design or find. That is not a coincidence. Conway chose the rules of GoL so that his conjecture would not be obviously true or false. Of all possible rules for a 2-D CA, most yield simple behavior: most initial conditions stabilize quickly or grow unboundedly. By avoiding uninteresting CAs, Conway was also avoiding Wolfram’s Class 1 and Class 2 behavior, and probably Class 3 as well.
If we believe Wolfram’s Principle of Computational Equivalence, we expect GoL to be in Class 4, and it is. The Game of Life was proved Turing complete in 1982 (and again, independently, in 1983). Since then, several people have constructed GoL patterns that implement a Turing machine or another machine known to be Turing complete.
Stable patterns in GoL are hard not to notice, especially the ones that move. It is natural to think of them as persistent entities, but remember that a CA is made of cells; there is no such thing as a toad or a loaf. Gliders and other spaceships are even less real because they are not even made up of the same cells over time. So these patterns are like constellations of stars. We perceive them because we are good at seeing patterns, or because we have active imaginations, but they are not real.
Well, not so fast. Many entities that we consider “real” are also persistent patterns of entities at a smaller scale. Hurricanes are just patterns of air flow, but we give them personal names. And people, like gliders, are not made up of the same cells over time. But even if you replace every cell in your body, we consider you the same person.
This is not a new observation—about 2500 years ago Heraclitus pointed out that you can’t step in the same river twice—but the entities that appear in the Game of Life are a useful test case for thinking about philosophical realism.
In the context of philosophy, realism is the view that entities in the world exist independent of human perception and conception. By “perception” I mean the information that we get from our senses, and by “conception” I mean the mental model we form of the world. For example, our vision systems perceive something like a 2-D projection of a scene, and our brains use that image to construct a 3-D model of the objects in the scene.
Scientific realism pertains to scientific theories and the entities they postulate. A theory postulates an entity if it is expressed in terms of the properties and behavior of the entity. For example, theories about electromagnetism are expressed in terms of electrical and magnetic fields. Some theories about economics are expressed in terms of supply, demand, and market forces. And theories about biology are expressed in terms of genes.
But are these entities real? That is, do they exist in the world independent of us and our theories?
Again, I find it useful to state philosophical positions in a range of strengths; here are four statements of scientific realism with increasing strength:
SR4 is so strong that it is probably untenable; by such a strict criterion, almost all current theories are known to be false. Most realists would accept something in the space between SR1 and SR3.
But SR1 is so weak that it verges on instrumentalism, which is the view that we can’t say whether a theory is true or false because we can’t know whether a theory corresponds to reality. Theories are instruments that we use for our purposes; a theory is useful, or not, to the degree that it is fit for its purpose.
To see whether you are comfortable with instrumentalism, consider the following statements:
“Entities in the Game of Life aren’t real; they are just patterns of cells that people have given cute names.”
“A hurricane is just a pattern of air flow, but it is a useful description because it allows us to make predictions and communicate about the weather.”
“Freudian entities like the Id and the Superego aren’t real, but they are useful tools for thinking and communicating about psychology (or at least some people think so).”
“Electric and magnetic fields are postulated entities in our best theories of electromagnetism, but they aren’t real. We could construct other theories, without postulating fields, that would be just as useful.”
“Many of the things in the world that we identify as objects are arbitrary collections like constellations. For example, a mushroom is just the fruiting body of a fungus, most of which grows underground as a barely-contiguous network of cells. We focus on mushrooms for practical reasons like visibility and edibility.”
“Some objects have sharp boundaries, but many are fuzzy. For example, which molecules are part of your body: Air in your lungs? Food in your stomach? Nutrients in your blood? Nutrients in a cell? Water in a cell? Structural parts of a cell? Hair? Dead skin? Dirt? Bacteria on your skin? Bacteria in your gut? Mitochondria? How many of those molecules do you include when you weigh yourself? Conceiving the world in terms of discrete objects is useful, but the entities we identify are not real.”
Give yourself one point for each statement you agree with. If you score 4 or more, you might be an instrumentalist!
If you are more comfortable with some of these statements than others, ask yourself why. What are the differences in these scenarios that influence your reaction? Can you make a principled distinction between them?
For more on instrumentalism, see http://en.wikipedia.org/wiki/Instrumentalism.
6.6 Implementing Life
The exercises at the end of this chapter ask you to experiment with and modify the Game of Life, and implement other 2-D cellular automata. This section explains my implementation of GoL, which you can use as a starting place for your experiments.
To represent the state of the cells, I use a NumPy array with type uint8, which is an 8-bit unsigned integer. As an example, the following line creates a 10 by 10 array initialized with random values of 0 and 1.
There are a few ways we can compute the GoL rules. The simplest
is to use
This implementation is a straightforward translation of the rules, but
it is verbose and slow. We can do better using cross-correlation, as
we saw in Section ??. There, we used
What we called a “window” in the context of 1-D correlation is
called a “kernel” in the context of 2-D correlation, but the idea
is the same:
Now we can use logical operators to compute the rules:
The first line computes a boolean array with
This version is faster, and probably good enough, but we can simplify it slightly by modifying the kernel:
This version of the kernel includes the center cell and gives it a weight of 10. If the center cell is 0, the result is between 0 and 8; if the center cell is 1, the result is between 10 and 18. Using this kernel, we can simplify the logical operations, selecting only cells with the values 3, 12, and 13.
That might not seem like a big improvement, but it allows one more simplification: with this kernel, we can use a table to look up cell values, as we did in Section ??.
This version is faster and more concise than the others; the only drawback is that it takes more explaining.
The code for this chapter is in the Jupyter notebook chap06.ipynb in the repository for this book. Open this notebook, read the code, and run the cells. You can use this notebook to work on the exercises in this chapter. My solutions are in chap06soln.ipynb.
Start GoL in a random state and run it until it stabilizes. What stable patterns can you identify?
Many named patterns are available in portable file formats.
One of the longest-lived small patterns is “rabbits”, which starts with 9 live cells and takes 17 331 steps to stabilize. You can get the initial configuration in various formats from http://www.conwaylife.com/wiki/Rabbits. Load this configuration and run it.
In my implementation, the
For example, one variation of GoL, called “Highlife”, has the same rules as GoL, plus one additional rule: a dead cell with 6 neighbors comes to life.
Write a class named
One of the more interesting patterns in Highlife is the replicator.
If you generalize the Turing machine to two dimensions, or add a read-write head to a 2-D CA, the result is a cellular automaton called a Turmite. It is named after a termite because of the way the read-write head moves, but spelled wrong as an homage to Alan Turing.
The most famous Turmite is Langton’s Ant, discovered by Chris Langton in 1986. See http://en.wikipedia.org/wiki/Langton_ant.
The ant is a read-write head with four states, which you can think of as facing north, south, east or west. The cells have two states, black and white.
The rules are simple. During each time step, the ant checks the color of the cell it is on. If black, the ant turns to the right, changes the cell to white, and moves forward one space. If the cell is white, the ant turns left, changes the cell to black, and moves forward.
Given a simple world, a simple set of rules, and only one moving part, you might expect to see simple behavior—but you should know better by now. Starting with all white cells, Langton’s ant moves in a seemingly random pattern for more than 10 000 steps before it enters a cycle with a period of 104 steps. After each cycle, the ant is translated diagonally, so it leaves a trail called the “highway”.
Write an implementation of Langton’s Ant.
Are you using one of our books in a class?We'd like to know about it. Please consider filling out this short survey.