- It's the end of the semester here in Madison, so I'm reaching into
my grab bag. You may notice that the Kitchen Shelf is mainly stocked with
2d CA images. The 1d possibilities have been intensively studied and
popularized by Wolfram, Langton and others. Interesting 3d dynamics are
still largely beyond the realm of effective computation and visualization.
Our mixmaster, CAM8, does have the processing power for some preliminary 3d
investigations that we hope to offer one of these weeks...
- For now, let's consider one of my favorite one-dimensional systems:
the basic 4-color cyclic cellular automaton started from a uniform random
configuration. The top row represents the initial random mix, and time
runs down, each successive update comprising one row. You can see that
each color 'eats' just one of the others, in a cyclic fashion. Evidently
the system clusters as time goes on. Simulation of the corresponding
five-color system, on the other hand, strongly suggests that every site
is painted with a final color, i.e., the system fixates. Maury
Bramson and I proved this clustering/fixation dichotomy for the
closely-related cyclic particle system, a continuous-time random process.
Bob Fisch then proved the same result for the CCA in his paper, "The
One-Dimensional Cyclic Cellular Automaton: a system with deterministic
dynamics that emulates an interacting particle system with stochastic
dynamics" Journal of Theoretical Probability 3, 311-338.
- Bob went on to study the rates of self-organization in the 3-
and 4- color CCA dynamics started from uniform random states. The former
model turns out to be exactly solvable, with average cluster size
C t ^.5 at time t, where C is a computable constant that
involves pi. The 4-color model pictured here is much more exotic:
extensive numerical simulations suggest a sub-diffusive rate
governed by a power law closer to 1/3 than 1/2. For details, see Fisch's
"Clustering in the one-dimensional three-color cyclic cellular automaton"
Annals of Probability 20, 1528-1548.
- The dynamics of cluster boundaries in many 1d systems can profitably
be analyzed as ballistic particle models. Here we see elementary edge
interactions such as annihilation and reflection. Simple collision rules
can lead to surprisingly complex aggregate behavior.