possible rules is out of the question except for elementary (d = 1, r **= 1) and** perhaps radius-two automata, one possible solution of the problem **consists in** using evolutionary algorithms, as first proposed by Packard in [15] and further developed by Mitchell et al. **in [5,4].**
The performance **of the best rules found at the end of the evolution is evaluated on a larger sample of ICs and it is defined as the fraction of correct**
classifications over n = 104**randomly chosen ICs. The ICs are sampled according to a binomial distribution (i.e., each bit is independently drawn with**
probability 1/**2 of being 0).** Mitchell and coworkers performed a number of studies on the emergence of synchronous CA strategies for the density task (with N **= 149) during evolution [5,4]. Their results are significant since they represent one of the few**
instances where the dynamics of emergent computation in complex, **spatially**
extended systems can be understood. In summary, these findings can be subdivided into those pertaining to the evolutionary history and those that are part of the "final" evolved automata. For the former, they essentially observed that, in successful evolution experiments, the fitness of the best rules increases in time according to rapid jumps, giving rise to what they call "epochs" in the evolutionary process. Each epoch corresponds roughly to a new, **increasingly**
sophisticated solution strategy. Concerning the final CA produced by evolution, it was noted that, in most runs, the GA found unsophisticated **strategies**
that consisted in expanding sufficiently large blocks of adjacent 1s or 0s. This
"block-expanding" strategy is unsophisticated in that it mainly uses **local information to reach a conclusion. As a consequence, only those IC that have**
low or high density are classified correctly since they are more likely to **have**
extended blocks of 1s or 0s. In fact, these CA have a performance around 0.6. However, some of the runs gave solutions that presented novel, more sophisticated features that yielded better performance (around 0.**77) on a wide**
distribution of ICs. However, high-performance automata have evolved only nine times out of 300 runs of the genetic algorithm. This clearly shows **that it**
is very difficult for genetic algorithm to find good solutions in this the search space.

These new strategies rely on traveling signals that transfer spatial and temporal information about the density in local regions through the lattice. An example of such a strategy is given in Figure 1, where the behavior of **the socalled GKL rule is depicted [4]. The GKL rule is hand-coded but its behavior**
is similar to that of the best solutions found by evolution. Crutchfield and coworkers have developed sophisticated methodologies for studying the transfer of long-range signals and the emergence of computation in evolved CA.

This framework is known as "computational mechanics" and it describes the intrinsic CA computation in terms of regular domains, particles, and particle interactions. Details can be found in [16,17,10]. Andre et al. **in [7] have been able to artificially evolve a better CA by using** genetic programming. Finally, Juill´e and Pollack [8] obtained still better CAs by using a coevolutionary algorithm. Their coevolved CA has performance