A fundamental problem in the theory of cellular automata is classification . A good classification divides cellular automata into groups with meaningfully related properties. In general there are two types of classifications: phenotypic and genotypic[2]. A phenotypic classification divides a population into groups according to their observed behavior. A genotypic classification divides a population into groups according to the intrinsic structure of the entities in the population. The most well-known classification of cellular automata, proposed by Wolfram[1], is a phenotypic classification. It attempts to account for a wide variety of of statistical, computational and dynamical systems properties cellular automata express in simulations. This letter contrasts the Wolfram classification with a genotypic classification based on mean field theory. It groups cellular automata according to the way they act on probability measures with no correlations between the states of cells separated in space. This letter demonstrates that some aspects of the behavior expressed by cellular automata are largely predictable on the basis of a genotypic classification.
The mean field theory is often used [6][5][4][3] to characterize individual cellular automata. Here the mean field theory is used to characterize the full space of cellular automaton rules. We view the mean field theory as a parametric representation of the space of cellular automata[7]. Each setting of parameter values corresponds to a subset of cellular automaton rules. As the parameter values are changed, the properties of the corresponding cellular automata change as well. The results below suggest that small changes in parameter values typically lead to small changes in the properties of the cellular automata described. In particular, if the majority of cellular automata with given parameter values are in a particular Wolfram class, then cellular automata with nearby parameter values will typically be in the same Wolfram class. Sharp changes in mean field behavior occur in some parameter ranges. These sharp changes herald changes in Wolfram class behavior of the corresponding rules.
The plan of this letter is as follows: The mean field theory classification of cellular automata is reviewed. Details have appeared elsewhere[7][5]. A correspondence between Wolfram classes and mean field classes is suggested. This correspondence is empirically examined for a two-parameter subspace of the mean field theory for radius one rules, and a one parameter subspace of radius three rules.