INTERNAL SYMMETRIES OF CELLULAR-AUTOMATA

(Internal) transformations on the space Sigma of automaton configurati ons are defined as bi-infinite sequences of permutations of the cell s ymbols. A pair of transformations (gamma, theta) is said to be an inte rnal symmetry of a cellular automaton f: Sigma --> Sigma f= theta(-1) f gamma. 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. Al gorithms to compute the symmetry homomorphism F and to classify automa ta by their symmetries are presented. Examples on the types of dynamic al implications of internal symmetries are discussed in detail. (C) 19 97 American Institute of Physics.