Complexity_ A Guided Tour - Melanie Mitchell [76]
It took a lot of staring at pictures like figure 11.4 for us to figure out what was going on. Luckily for us, Jim Crutchfield, a physicist from Berkeley, happened to visit the Santa Fe Institute and became interested in our effort. It turned out that Jim and his colleagues had earlier developed exactly the right conceptual tools to help us understand how these patterns implement the computation.
FIGURE 11.4. Space-time behavior of one of the best-performing evolved cellular automaton rules for the majority classification task. In (a), the initial configuration contains a majority of black cells and the cellular automaton iterates to a fixed configuration of all black. In (b), the initial configuration contains a majority of white cells and the cellular automaton iterates to a fixed configuration of all white. (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.)
Three types of patterns can be seen in figure 11.4: all black, all white, and a checkerboard-like region of alternating black and white states (this appears as a grayish region in the low-resolution figure 11.4). It is this checkerboard pattern that transfers information about the density of black or white cells in local regions.
Like the strategy the genetic algorithm evolved for Robby the Robot, the cellular automaton’s strategy is quite clever. Take a look at figure 11.5, which is a version of figure 11.4a that I have marked up. Regions in which the initial configuration is either mostly white or mostly black converge in a few time steps to regions that are all white or all black. Notice that whenever a black region on the left meets a white region on the right, there is always a vertical boundary between them. However, whenever a white region on the left meets a black region on the right, a checkerboard triangle forms, composed of alternating black and white cells. You can see the effect of the circular lattice on the triangle as it wraps around the edges.
Sides A and B of the growing checkerboard region travel at the same velocity (i.e., distance covered over time). Side A travels southwest until it collides with the vertical boundary. Side B just misses colliding with the vertical boundary on the other side. This means that side A had a shorter distance to travel. That is, the white region bordered by side A is smaller than the black region bordered by side B. At the collision point, side A disappears, and the black region is allowed to grow. At the triangle’s bottom point, sides B and C disappear, and the entire lattice becomes black, the correct final configuration.
FIGURE 11.5. The space-time diagram of figure 11.4 (a) with important features marked.
If we try to understand these patterns as carrying out a computation, then the vertical boundary and the checkerboard region can be thought of as signals. These signals are created and propagated by local interactions among cells. The signals are what allow the cellular automaton as a whole to determine the relative sizes of the larger-scale adjacent black and white regions, cut off the smaller ones, and allow the larger ones to grow in size.
These signals are the major difference between the local majority voting cellular automaton of figure 11.1 and the cellular automaton of figure 11.5. As I mentioned above, in the former there is no way for separated black or white regions to communicate with one another to figure out which has the majority of cells. In the