The Cook Book

Recipe for the week of May 15 - 21

The 4-Color CCA in One Dimension

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.

Take me higher...
Introduction to the PSK PSK Search Recent Additions CA Archive CA Links Feedback Appreciated !