Distribution of Linear Rules in Cellular Automata Rule Space
Ron Bartlett
Institute for Intelligent Systems, Memphis State University,
Memphis, TN 38152, USA
Max Garzon
LIP-Ecole Normale Superieure,
46, Allee d'Italie, 69364 Lyon Cedex 07, France
Abstract
We attempt to find a good linear (that is, additive) approximation of a given rule by looking at the geometric-combinatorial properties of rule space with a Hamming distance. We show that all linear rules are equidistant from one another for a prime number of states, and that several parameters describing the geometry of rule space are essentially preserved in the subspace of linear rules. This is particularly true of the average and maximum distance between rules. The fit improves as the number of states grows toward the thermodynamic limit. In particular, linear rules provide a well-distributed initial population for a genetic search of CA rule space. We achieve asymptotically exact solutions for the nearest approximation to a given rule from an initial population of piecewise linear rules obtained by splicing, a modification of the standard genetic crossover operator.
