Internal symmetries of cellular automata

(Internal) transformations on the space Σ of automaton configurations are defined as bi-infinite sequences of permutations of the cell symbols. A pair of transformations (γ, θ) is said to be an internal symmetry of a cellular automaton f: Σ → Σ if f=θ-1 f γ. It is shown that the full group of internal symmetries of an automaton f can be encoded as a group homomorphism F such that θ=F(γ). The domain and image of the homomorphism F have, in general, infinite order and F is presented by a local automaton-like rule. Algorithms to compute the symmetry homomorphism F and to classify automata by their symmetries are presented. Examples on the types of dynamical implications of internal symmetries are discussed in detail. © 1997 American Institute of Physics.

VIVO