Chapter 7 Game of LifeOne 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. 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 8 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:
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:
7.1 Implementing LifeTo implement GoL efficiently, we can take advantage of the multidimensional convolution function in SciPy. SciPy is a Python package that provides functions related to scientific computing. You can read about it at http://www.scipy.org/; if it is not already on your system, you might have to install it. Convolution is an operation common in digital image processing, where an image is an array of pixels, and many operations involve computing a function of a pixel and its neighbors. The neighborhood is described by a smaller array, called a kernel that specifies the location and weight of the neighbors. For example, this array: kernel = numpy.array([[1,1,1], [1,0,1], [1,1,1]]) represents a neighborhood with eight neighbors, all with weight 1. Convolution computes the weighted sum of the neighbors for each element of the array. So this kernel computes the sum of the neighbors (not including the center element). For example, if array represents a GoL grid with 1s for live cells and 0s for dead cells we can use convolution to compute the number of neighbors for each cell. import scipy.ndimage neighbors = scipy.ndimage.filters.convolve(array, kernel) Here’s an implementation of GoL using convolve: import numpy import scipy.ndimage class Life(object): def __init__(self, n, mode='wrap'): self.n = n self.mode = mode self.array = numpy.random.random_integers(0, 1, (n, n)) self.weights = numpy.array([[1,1,1], [1,10,1], [1,1,1]]) def step(self): con = scipy.ndimage.filters.convolve(self.array, self.weights, mode=self.mode) boolean = (con==3)  (con==12)  (con==13) self.array = numpy.int8(boolean) The attributes of the Life object are n, the number of rows and columns in the grid, mode, which controls the behaviors of the boundary cells, array, which represents the grid, and weights which is the kernel used to count the neighbors. The weight of the center cell is 10, so the number of neighbors is 08 for dead cells and 1018 for live cells. In step, boolean is a boolean array with True for live cells; numpy.int8 converts it to integers. To display an animated sequence of grids, I use pyplot. Animation in pyplot is a little awkward, but here’s a class that manages it: import matplotlib matplotlib.use('TkAgg') import matplotlib.pyplot as pyplot class LifeViewer(object): def __init__(self, life, cmap=matplotlib.cm.gray_r): self.life = life self.cmap = cmap self.fig = pyplot.figure() pyplot.axis([0, life.n, 0, life.n]) pyplot.xticks([]) pyplot.yticks([]) self.pcolor = None self.update() life is a Life object. cmap is a color map provided by matplotlib; you can see the other color maps at http://www.scipy.org/Cookbook/Matplotlib/Show_colormaps. self.fig is a reference to the matplotlib figure, and self.pcolor is a reference to the pseudocolor plot created by update: def update(self): if self.pcolor: self.pcolor.remove() a = self.life.array self.pcolor = pyplot.pcolor(a, cmap=self.cmap) self.fig.canvas.draw() If there is already a plot, we have to remove it; then we create a new one and invoke draw to update the display. To run the animation, we need two methods: def animate(self, steps=10): self.steps = steps self.fig.canvas.manager.window.after(1000, self.animate_callback) pyplot.show() def animate_callback(self): for i in range(self.steps): self.life.step() self.update() animate gets the animation started. It invokes pyplot.show,
which sets up the GUI and waits for user events, but first it has
to invoke window.after to set up a callback, so that
Exercise 1 Download my implementation of GoL from thinkcomplex.com/Life.py. Start the CA in a random state and run it until it stabilizes. What stable patterns can you identify? 7.2 Life patternsIf you run GoL from a random starting state, a number of stable patterns are likely to appear. Blocks, boats, beehives, blinkers and gliders are among the most common. People have spent embarrassing amounts of time finding and naming these patterns. If you search the web, you will find many collections. From most initial conditions, GoL quickly reaches a stable state where the number of live cells is nearly constant (usually with a small amount of 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 longlived. One of the simplest is the rpentomino, which has only five cells in the shape of a “r,” hence the name. It runs for 1103 steps and yields 6 gliders, 8 blocks, 4 blinkers, 4 beehives, 1 boat, 1 ship, and 1 loaf. One of the longestlived small patterns is rabbits, which starts with 9 live cells and takes 17 331 steps to stabilize. Exercise 2 Start with an rpentomino as an initial condition and confirm that the results are consistent with the description above. You might have to adjust the size of the grid and the boundary behavior. 7.3 Conway’s conjectureThe existence of longlived patterns brings us back to Conway’s original question: are there initial patterns that never stabilize? Conway thought 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. Gosper also discovered the first puffer train. You can find descriptions and animations of these patterns in several places on the Web. 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 the possible rules for a 2D 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. Exercise 3 Many named patterns are available in portable file formats. Modify Life.py to parse one of these formats and initialize the grid. 7.4 RealismStable 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. Right? 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 2D projection of a scene, and our brains use that image to construct a 3D 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, Mendelian genetics postulates a “gene” as a unit that controls a heritable characteristic. Eventually we discovered that genes are encoded in DNA, but for about 50 years, a gene was just a postulated entity. See http://en.wikipedia.org/wiki/Gene. Again, I find it useful to state philosophical positions in a range of strengths, where SR1 is a weak form of scientific realism and SR4 is a strong form:
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. 7.5 InstrumentalismBut 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).” “Electrons are postulated entities in our best theories of electromagnetism, but they aren’t real. We could construct other theories, without postulating electrons, 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 barelycontiguous 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? Exercise 4 Read http://en.wikipedia.org/wiki/Instrumentalism and construct a sequence of statements that characterize instrumentalism in a range of strengths. 7.6 TurmitesIf you generalize the Turing machine to two dimensions, or add a readwrite head to a 2D CA, the result is a cellular automaton called a Turmite. It is named after a termite because of the way the readwrite 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 readwrite 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 is it on. If it is 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.” If you start with multiple Turmites, they interact with each other in seemingly complex ways. If one Turmite is on the highway, another can follow it, overtake it, and cause it to reverse its pattern, moving back up the highway and leaving only white cells behind. 
Like this book?
Are you using one of our books in a class?We'd like to know about it. Please consider filling out this short survey.
