Cellular automata are dynamical systems in which space, time, and the states of the system are discrete. Each cell in a regular lattice changes its state with time according to a rule which is local and deterministic. All cells on the lattice obey the same rule. This class of dynamical systems has been extensively studied as a model of natural systems in which large numbers of simple individuals interact locally so as to give rise to globally complex dynamics.
Study of cellular automata has given rise to the ``edge of chaos" (EOC) hypothesis. In its basic form, this is the hypothesis that in the space of dynamical systems of a given type, there will generically exist regions in which systems with simple behavior are likely to be found, and other regions in which systems with chaotic behavior are to be found. Near the boundaries of these regions more interesting behavior, neither simple nor chaotic, may be expected.
Early evidence for the existence of an edge of chaos has been reported by Langton [Lan86,Lan90] and Packard [Pac88]. Langton based his conclusion on data gathered from a parameterized survey of cellular automaton behavior. Packard, on the other hand, used a genetic algorithm [Hol75] to evolve a particular class of complex rules. He found that as evolution proceeded the population of rules tended to cluster near the critical region identified by Langton.
The validity of some of these results have been called into question by Mitchell, Crutchfield, and coworkers ([MHC93,MCH94,DMC94]) These authors performed experiments in the spirit of Packard's. They found that while their genetic algorithm indeed produced increasingly complex rules, the cellular automata generated could not be considered to reside at a separatrix between simple and chaotic dynamical regimes.
The edge of chaos is a stimulating idea in that it promises to provide a framework in which to relate methods and results originating in biology, physics, and computer science. Yet the very generality and cross-disciplinary nature of the edge of chaos concept has lead to enormous difficulties of communication between workers from different background attempting to make these intuitions rigorous by the standards of their discipline.
We can divide the evolution toward the edge of chaos issue into several sub-issues:
In this paper we clarify a subset of the issues surrounding the edge of chaos theme. We restrict ourselves to study of the edge of chaos in the context of cellular automata. It is in this context that these issues were originally brought forward. We note, however, that an important advance was made by Suzuki and Kaneko [KS93,SK94] who used the logistic map, with a well-defined transition of chaos, as the basis for genetic evolution. They found that under a suitable dynamic, evolution indeed proceeded toward this transition.
Of the many objections that have been raised to EOC, we focus
mainly on one:
that the large variability of behavior for cellular
automata with a given 
value makes the identification
of a sharp "edge" of chaos difficult. We show that variability
can be drastically reduced by moving to a more refined parameterization
of cellular automata. When this new parameter space is
projected into the 
parameter space, sharper transitions
are found at the same locations predicted by earlier work using
alone.
We use the mean field theory as our primary tool. It provides us with an analytic handhold on the relationship between parameterizations of the space of cellular automata, and the evolutionary construction of complex rules. The mean field theory allows us to 1) locate with some precision regions of rule space which contain particularly complex rules, and 2) to perform genetic evolution in such a way as to at once produce increasingly complex rules, and to approach a region in parameter space where the domains of simple and chaotic rules adjoin.