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.