Explorations in the World of Cellular Automata
Take lots of simple 2-state components that are identical with one
another, arrange them in a regular array, and prescribe some rule by which
each component influences the way its closest neighbors change states.
The resulting system is called a "cellular automaton" or CA. If some
randomness is involved in the state changes, then you get a "probabilistic
cellular automaton" or PCA.
CA's and PCA's have several nice features:
1. They can be described without much difficulty to anyone who has a
minimal amount of mathematical sense.
2. They can exhibit a rich variety of complex behaviors.
3. They are the subject of a great deal of on-going research, often with
practical implications (physics, ecology, computer science, etc.)
4. There are several free computer programs available for performing
experimentation on the most interesting classes of CA's and PCA's.
In our explorations, we will focus on a few of my favorite systems:
1. A simple model for traffic flow that provides insights into the
formation of traffic jams.
2. Two models due to the physicist Per Bak, described in his book
"How Nature Works"; one is a simple model of evolution, the other
is related to certain types of avalanches.
3. Models capable of arbitrarily complicated behavior (universal
computation), including the most famous of all CA's, Conway's "Game of
Life".
4. Cyclic CA's, just because they are so much fun.
There will be two main mathematical themes:
1. The mysterious emergence of complex cooperative phenomena in systems
with absurdly simple individual components.
2. What happens when you turn a CA into a PCA by introducing random state
changes at a small rate; are the behaviors exhibited by the CA stable?
The prerequisites are: some familiarity with the basic rules of
probability, and some ability to cope with standard mathematical notation,
such as sub- and superscripts, set operations like union and intersection,
xy-coordinates, and the like. If you want a headstart, visit David
Griffeath's website at http://psoup.math.wisc.edu/welcome.html, which
is the world's premier site about CA's, with lots of links to other sites,
and free downloads of excellent Windows programs for simulating CA's and
PCA's.