Automorphissm Classification of Cellular Automata

Abstract

A new classification of arbitrary cellular automata (CA for short) in Z^d is studied considering the set (group) of all permutations of the neighborhood ν and state set Q. Two CA (Z^d, Q, f_A, ν_A) and (Z^d, Q, f_B, ν_B) are called automorphisc, if there is a pair of permutations (π, �) of ν and Q, respectively, such that (f_B, ν _B) = (�⁻¹ f_A^π�, ν_A^π), where ν^π denotes a permutation of ν and f^π denotes a permutation of arguments of local function f corresponding to ν ^π. This automorphissm naturally induces a classification of CA, such that it generally preserves the global properties of CA up to permutation. As a typical example of the theory, the local functions of 256 ECA (1-dimensional 3-nearest neighbors 2-states CA) are classified into 46 classes. We also give a computer test of surjectivity, injecitivity and reversibility of the classes.