Cyclic Cellular Automata in Two Dimensions
Robert O. Fisch, Janko Gravner, David S. Griffeath · Birkhäuser Boston eBooks · 1991
Start by randomly populating each site of the two-dimensional integer lattice with any one of N types, labeled 0, 1,... ,N-1 (N ≥ 3). The type ζ(y) at site y can eat the type ζ(x) at neighboring site x (i.e., replace the type at x with ζ(y)) provided that ζ(y) — ζ(x) = 1 mod iV. We describe the dynamics of cyclic cellular automata (c.c.a.) ζt , discrete-time deterministic systems which follow the rule:(●) At any time t, each type ζt(y) eats every neighboring type that it can.These systems have remarkably complex dynamics. As N becomes large they display a curious metastability leading to large-scale locally-periodic structure. This article contains a preliminary account of our findings. For the most part, we rely on computations and computer graphics produced by the Cellular Automaton Machine. However we are able to give a simple proof that the infinite system ζt is asymptotically locally periodic for any N > ∞. Moreover, we identify a number of regularity properties of rule (●), mostly topological in nature, that offer some hope for a more detailed rigorous analysis.