## 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.