In the previous chapter we used PyLab to generate a graphical representation of the evolution of a 1-D cellular automaton. Using pylab.pcolor is easy but for large numbers of cells the performance is a little slow. Also, the Postscript PyLab generates is not very efficient. For the figures in this book, I wrote some Python code that generates small, fast Postscript. Along the way, I also wrote code to generate GIF images using the Python Imaging Library (PIL).
I ended up with three different ways to draw a CA, and it was a challenge to organize the code in a sensible way. I ended using a design pattern called an abstract type (see wikipedia.org/wiki/Abstract_type).
An abstract type is a class definition that defines an interface, but leaves the implementation of the interface unspecified. As an example, here is the definition of a class named Drawer:
class Drawer(object):
def draw(self, ca):
"""draw a representation of cellular automaton (ca).
This function generally has no visible effect."""
def show(self):
"""display the representation on the screen, if possible"""
def save(self, filename):
"""save the representation of the CA in (filename)"""
These methods have no statements in the body, only dosctrings. It is up to the subclasses to provide implementations. In my program, I defined three subclasses that inherit from Drawer: PyLabDrawer, which uses pylab.pcolor, PILDrawer, which uses PIL and Tkinter to generate and display a GIF, and EPSDrawer, which generates encapsulated postscript.
Some programming languages provide explict support for abstract types, so they can generate appropriate error messages if something goes wrong. For example, it is usually illegal to instantiate an abstract type—it doesn’t provide an implementation, so it can’t really do anything. Python does not enforce this rule, so it is possible (but not very useful) to instantiate a Drawer. In Python, it is up to the programmer to use abstract types correctly.
Rewrite your code from the previous chapter using Drawer as an abstract type. One of the advantages of this reorganization is that you should can separate the CA code from the graphics code. All of the code that pertains to PyLab should be moved into the definition of PyLabDrawer.
Then write another implementation of a Drawer that uses PIL to generate a GIF. To get you started, you can download greenteapress.com/compmod/pil.py, which contains example code that creates an image, draws a rectangle, displays the image using Tkinter, and generates a GIF.
Finally, if you are familiar with Postscript, write a third implementation of Drawer that generates encapsulated Postscript. Or you might consider writing an implementation using a Tkinter Canvas.
You can download my solution from greenteapress.com/compmod/CADrawer.py
One of the first cellular automata to be studied, and probably the most popular of all time, 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.
The cells in GoL are arranged in a 2-D grid, either infinite in both directions or wrapped in both directions. A grid that is wrapped in both directions is called a torus because it is topographically equivalent to the surface of a doughnut (see 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:
| Number of | Current | Next |
| neighbors | state | state |
| 2–3 | live | live |
| 0–1,4–8 | live | dead |
| 3 | dead | live |
| 0–2,4–8 | dead | dead |
GoL turned out to be popular because
Write a class that implements a “Game of Life” CA, and another class that displays an animated sequence of timesteps on the screen.
Remember that all cells have to be updated “simultaneously;” for example, if you traverse an array and update cells as you go, you will end up using some new values in subsequent updates. The result is not a correct implementation of Conway’s rules.
There are many implementation options:
Try to choose an implementation that can update and display a large CA quickly1.
Start the CA in a random state and run it until it stabilizes. What stable patterns can you identify?
If 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 embarassing amount of time finding (and naming) these patterns. If you search the web, you will find many collections.
Many named patterns are available in portable file formats. Modify your program to parse one of them in order to place patterns into your grid and run them.
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 long-lived. One of the simplest is the r-pentomino, 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 longest-lived small patterns is rabbits, which starts with 9 live cells and takes 17 331 steps to stabilize.
These long-lived patterns bring 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 an 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 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 should expect GoL to be in Class 4. And it is. The Game of Life was proven to be 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.
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 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 posulate. 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.
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).”
“Electrons are postulated entities in our best theories of electro-magnetism, 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 abritrary 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 with others, ask youself why. What are the differences in these scenarios that influence your reaction? Can you make a principled distinction between them?
Read the Wikipedia page on instrumentalism and construct a sequence of statements that characterize instrumentalism in a range of strengths.
If you generalize the Turing machine to two dimensions or add a read-write head to a 2-D CA, either way you get 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 Turing.
One of the most famous Turmites is Langton’s Ant, discovered by Chris Langton in 1986. 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 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 linear 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.
Read wikipedia.org/wiki/Langton's_ant.
Swampy includes a module called TurmiteWorld that contains an implementation of Langton’s Ant. Read the code to get a sense of how it works, then run it with a variety of initial conditions.
The CAs we have seen so far are not physical models; that is, they are not intended to describe systems in the real world. As it turns out, there are some real systems that have the same structure as a CA. For example, Wolfram has argued that patterns on some animals, especially cone snails, may be generated by processes that are equivalent to a CA (see stephenwolfram.com/publications/articles/ca/83-cellular/2/text.html).
But some CAs are designed explicitly as physical models. In this section we will consider a simple grid-based model of percolation; in the next chapter we will see examples that model forest fires, avalanches, and earthquakes.
Percolation is a process in which a fluid flows through a semi-porous material. Examples include oil in porous rock, water in paper, and hydrogen gas in micropores. Percolation models are also used to study systems that are not literally percolation, including epidemics and networks of electrical resistors.
Percolation processes often exhibit a phase change; that is, an abrupt transition from one behavior (low flow) to another (high flow) with a small change in a continuous parameter (like the porosity of the material). This transition is sometimes called a “tipping point.”
You can model this phase change with a simple grid-based system (it is not really a CA because it does not evolve in time). The cells in the grid can have two states, representing a porous segment of the material or a non-porous segment. The states of the cells are random; the probability that any cell is porous is specified by the parameter p.
In the context of percolation models, a porous segment is called a “bond.” A “path” is a sequence of bonds where each bond in the sequence is adjacent to the next in the grid. A “cluster” is a set of bonds where there is a path from every bond to every other bond.
The rate of flow in a percolation system is primarily determined by whether or not the porous cells form a path all the way through the material, so it is useful to know whether a set of bonds contains a “spanning cluster.” There are several possible definitions of a spanning cluster; the choice depends on the system you are trying to model. The simplest choice is a cluster that reaches the top and bottom row of the grid.
For a given value of p, you can estimate R(p), which is the probability that there is a spanning cluster, by generating a large number of random grids and computing the fraction that contain a spanning cluster. This way of estimating probabilities is called a “Monte Carlo simulation” because it a similar to a game of chance.
Percolation models are often used to compute the critical value, pc, which is the fraction of porous segments where the phase change occurs; that is, where the probability of a spanning cluster increases quickly from near 0 to near 1.
The paper “Efficient Monte Carlo Algorithm and High-Precision Results for Percolation,” by Newman and Ziff, presents an efficient algorithm for checking whether there is a path through a grid. Read this paper, implement their algorithm, and see if you can reproduce their Figure 2(a).