Parameterizing the Space of CA Rules

An important hierarchy of parameterization schemes based on successive refinements to a mean-field theoretic description, called local structure theory, has been developed by Gutowitz, et. al. ([guto87a], [guto87b], and [guto88]), and is discussed in detail in chapter five. Below we summarize results of what is essentially a zeroth order local structure theory developed by Langton [lang90]. 

Consider an arbitrary d dimensional, k state CA with neighborhood of size Af and evolving in time according to the transition rule f . Denoting the space of all possible rules for this CA by we recall that the number of such rules is =  

Although the analogy is not perfect, this parameter can be thought of as a temperature in statistical physics or as the degree of non-linearity in a dynamical system. 

The idea now is to use A to systematically sample, and study the behavior of, rules in the rule space starting with one-dimensional CA. The sections below 

Consider the behavioral changes induced in a randomly chosen one-dimensional CA rule such that A is successively and minimally incremented from 0 to 1. As an example, let us take fc = 4 and r = 2 (i.e. neighborhood size M = 2r + 1), and use a lattice of = 128 sites with periodic boundary conditions. We summarize a typical sequence of induced behavioral cdianges  

---

The LST is a finitely parameterized model of the action of a given CA rule, >, on probability measures on the space of configurations on an arbitrary lattice. In a very simple manner - which may be thought of as a generalization of the simple mean field theory (MFT) introduced in section 3.1.3. - the LST provides a sequence of approximations of the statistical features of evolving CA patterns. 

Langton was able to provide a tentative answer to his question - at least within the somewhat more limited realm of the complex dynamics of CA - by examining the behavior of the entire rule space of elementary one-dimensional CA rules as parameterized by a single parameter A (see section 3.2.1). Given a rule 4>, A is defined to be the fraction of entries in the rule table for [Pg.683]

---