Automorphisms of Transition Graphs for Elementary Cellular Automata
Edward J. Powley and Susan Stepney
The transition graph of a cellular automaton (CA) is a graphical representation of the CA’s global dynamics. Studying automorphisms of transition graphs allows us to identify symmetries in this global dynamics. We conduct a computational study of numbers of automorphisms for the elementary cellular automata (ECAs) on finite lattices. The ECAs are partitioned into three classes, depending on how the number of automorphisms varies as a function of the number of cells in the lattice. While one of these classes contains the majority of the ECAs, and encompasses dynamical behaviour ranging from trivial to complex, the other two classes identify those ECAs whose local rule is a non-trivial linear function of its inputs, as well as those ECAs capable of producing chaotic dynamics from ordered initial configurations, and a small number of other “exceptional” ECAs.