Complexity_ A Guided Tour - Melanie Mitchell [77]
Jim Crutchfield had earlier invented a technique for detecting what he called “information processing structures” in the behavior of dynamical systems and he suggested that we apply this technique to the cellular automata evolved by the GA. Crutchfield’s idea was that the boundaries between simple regions (e.g., sides A, B, C, and the vertical boundary in figure 11.5) are carriers of information and information is processed when these boundaries collide. Figure 11.6 shows the space-time diagram of figure 11.5, but with the black, white, and checkerboard regions filtered out (i.e., colored white), leaving only the boundaries, so we can see them more clearly. The picture looks something like a trace of elementary particles in an old physics device called a bubble chamber. Adopting that metaphor, Jim called these boundaries “particles.”
Traditionally in physics particles are denoted with Greek letters, and we have done the same here. This cellular automaton produces six different types of particles: γ (gamma), μ (mu), η (eta), δ (delta), β (beta), and α (alpha, a short-lived particle that decays into γ and μ). Each corresponds to a different kind of boundary—for example, η corresponds to boundaries between black and checkerboard regions. There are five types of particle collisions, three of which (β + γ, μ + β, and η + δ) create a new particle, and two of which (η + μ and γ + δ) are “annihilations,” in which both particles disappear.
Casting the behavior of the cellular automaton in terms of particles helps us understand how it is encoding information and performing its computation. For example, the α and β particles encode different types of information about the initial configuration. The α particle decays into γ and μ. The γ particle carries the information that it borders a white region; similarly, the μ particle carries the information that it borders a black region. When γ collides with β before μ does, the information contained in β and γ is combined to deduce that the large initial white region was smaller than the large initial black region it bordered. This new information is encoded in a newly created particle η, whose job is to catch up with and annihilate the μ (and itself).
FIGURE 11.6. The space-time diagram of figure 11.4(a), with regions of “simple patterns” filtered out, leaving the boundaries between these regions (“particles”). (Figure adapted from Mitchell, M., Crutchfield, J. P., and Das, R., Evolving cellular automata to perform computations: A review of recent work. In Proceedings of the First International Conference on Evolutionary Computation and Its Applications (EvCA ’96). Moscow, Russia: Russian Academy of Sciences, 1996.)
We were able to apply this kind of analysis to several different cellular automata evolved to perform the majority classification task as well as other tasks. This analysis allowed us to predict things such as the fitness of a given cellular automaton (without having to run the cellular automaton itself, but using only its “particle” description). It also allowed us to understand why one cellular automaton had higher fitness than another and how to describe the mistakes that were made by different cellular automata in performing computations.
Particles give us something we could not get by looking at the cellular automaton rule or the cellular automaton’s space-time behavior alone: they allow us to explain, in information-processing terms, how a cellular automaton performs a computation. Note that particles are a description imposed by us (the scientists) rather than anything explicit taking place in a cellular automaton or used by the genetic algorithm to evolve cellular automata. But somehow the genetic algorithm managed to evolve a rule whose behavior can be explained in terms of information-processing particles. Indeed, the language