Internal symmetries of cellular automata.

(Internal) transformations on the space Sigma of automaton configurations are defined as bi-infinite sequences of permutations of the cell symbols. A pair of transformations (gamma,theta) is said to be an internal symmetry of a cellular automaton f:Sigma-->Sigma if f=theta(-1)fgamma. It is shown that the full group of internal symmetries of an automaton f can be encoded as a group homomorphism F such that theta=F(gamma). 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. (c) 1997 American Institute of Physics.