Paul Grobstein, Bryn Mawr College Department of Biology
Clare Congdon, Bryn Mawr College Computer Science Program

Lab 3: Cellular Automata

You should now have a sense that quite unexpected and interesting things can happen with even a very small number of non-linear interactions. Among the things that should be emphasized is that the "unexpected" behavior is not only not specified in the underlying rules but is in general neither anticipatable or observable except by "running" such systems. Hence, one can make quite novel observations (which might or might not turn out to be meaningful in other contexts) simply by conceiving simple sets of non-linear interactions and "seeing what happens".

The Game of Life, conceived by the mathematician John Conway, is a case in point. Conway specifically set out to create an "interesting" system, one which displayed behavior which was "unexpected" (but not TOO unexpected, as in completely random behavior). The interacting elements (agents) are quite simple, and consist of locations in a two dimensional orthogonal grid (cells) which can be in one of two states (alive or dead). The rules of interaction are almost as simple: a live cell remains alive if either two or three of its eight neighbors are alive, and otherwise it dies; a dead cell becomes alive if three neighbors are alive. The rules are arbitrary, and reflect Conway's explorations; can you explain why they are "non-linear"?

Despite the simplicity of the game, its behavior is so unexpected (in the sense defined above) that, more than twenty-five years after its creation, people are still discovering new things about it, as well as exploring the extent to which its behavior might help to explain other phenomena.

The Game of Life is an instance of a more general set of models, called Cellular Automata. By changing the rules of interaction, one gets new models and new behaviors. One can also imagine altering the number of states that any cell can take up, as well as altering the number and metric of their distribution in space. If the Game of Life is still generating interesting behaviors, one can imagine how many lifetimes would need to be invested to explore the set of all possible cellular automata. To be emphasized is that, in most cellular automata models, the "unexpected" behavior does not result from any randomness; the systems are (like that studied last week) are fully deterministic.

An additional noteworthy characteristic is the enormous sophistication of behaviors displayed by systems in which elements (agents) are fixed in space (unlike the freedom to move as in StarLogo models). Your primary assignment for this week is to get a feeling for this, and develop what intuitions you can about the properties of cellular automata. To do so, you may want to stay with the Game of Life and explore questions like how many possible "forms" can emerge, how much does the forms depend on starting conditions, or can particular kinds of patterns or computations be created? Alternatively, you may want to explore one or another variant, either in comparison to the Game of Life or in its own right. An interesting variant, for example, is called Fredkins's Rule and involves simply changing the rules of interaction so that a cell becomes alive if and only if the number of living neighbors in odd (and becomes dead if it is even).

Like last week, you should record your observations in your online journal. You should also, like last week, be advancing your modelling skills, exploring the web in relation to complex systems, and thinking about your first project.

Caveat:
LifeLab does not seem to work properly. It works fine for the Game of Life, but is buggy with other CA's. If you're interested, figure out what does and doesn't work; otherwise, let it go and use LifeMaker instead.

Some Specific Things to Try:

1. The Game of Life:

   A cell becomes alive if it has exactly 3 live neighbors. If it has 2 live neighbors, it stays the way it was (if it was alive, it stays alive, if it was dead, it stays dead). For more than 3 or less than 2 live neighbors, the cell will be dead.

   Set up this rule and try a few different initial patterns to see what happens.

2. Glider guns, etc., as decribed in Sigmund, Chapter 2

3. Fredkin's Rule:

   A cell becomes "alive" if and only if the number of living neighbors is odd.

   Set up this rule and try a few different initial patterns to see what happens.

   Something to try with Fredkin's Rule:
   Make grid have a "live" border around a solid mass of "dead" cells and use Fredkin's rule. Or try another pattern with horizontal and vertical lines that extent the height and width of the grid.

4. Find Some Interesting Patterns on Your Own:

   Play around a little bit with the different possible rules and different possible initial setups.