Conservation laws in cellular automata

Abstract

If X is a discrete abelian group and A a finite set, then a cellular automaton (CA) is a continuous map F: AX−→A X that commutes with all X-shifts. If φ: A−→R, then, for any a ∈ AX, we define Σφ(a) = ∑ x∈X φ(ax) (if finite); φ is conserved by F if Σφ is constant under the action of F. We characterize such conservation laws in several ways, deriving both theoretical consequences and practical tests, and provide a method for constructing all onedimensional CA exhibiting a given conservation law. If A is a finite set (with discrete topology), and X an arbitrary indexing set, then AX (the space of all functions X ↦ → A) is compact and totally disconnected in the Tychonoff topology. If (X, +) is a discrete abelian group1 (eg. X = ZD) with identity O, then X acts on itself by translation; this induces a shift action of X on AX: if a = [ax | x∈X] ∈ AX, and u ∈ X, then σu (a) = [bx | x∈X], where bx = a(x+u). A cellular automaton (CA) is a continuous map F: AX − → AX which commutes with all shifts. The Curtis-Hedlund-Lyndon Theorem [3] says that F is a CA if and only if there is some finite B ⊂ X (a “neighbourhood of the identity”) and a local map f: AB−→A so that, for all a ∈ A X and x ∈ X, F(a)x = f