The Discovery of Complex Rules

Introduction

After Wolfram’s proposal, other authors analyzed systems of CAs and proposed their own classifications (Gutowitz 1990; Li, Packard, and Langton 1990). Kurka (1997) proposed to classify them in 5 groups, based on the structure of their attractors. Walker (1990) based his characterization on connected Boolean networks. Many other researchers proposed classifications based on rule sets governing the CAs’ behavior (Barbe 1990; Jen 1990; McIntosh,1990; Voorhees, 1990; Wootters & Langton 1990).

In previous chapters, we argued that the rules that best describe the behavior of biological systems are what Wolfram (1984, 2002) calls “complex rules”. CAs with complex rules have the ability to process information. In other words, they are universal computers. If a system is capable of universal computation, the evolution of the system from a given set of starting conditions represents a finite computational process. A universal computer can mimic any other system generating a limitless range of complex behaviors. In these circumstances, it is not surprising that the search for complex rules and the analysis of their behavior has been one of the key themes in Complexity Science and Artificial Life. The proof that several CA systems are universal computers is based on Conway’s Game of Life (Gardner 1983). The proof is based on the demonstration that CAs can generate structures corresponding to the components of an idealized digital computer. By connecting these components in different configurations it is possible to implement any algorithm, just as any known algorithm can be implemented on the simpler and better known Turing Machine. (Smith, 1971). Underlying Wolfram’s characterization and classification of the behavior of Cellular Automata are two key questions (Wolfram 1994):

• 1.

  Is it possible to predict the global behavior of an automaton from knowledge of its local rules (the bottom up approach)?;

• 2.

  Is it possible to design local rules that generate complex behaviors (the inverse, top-down problem)?

Deducing complex behaviors from local rules is extremely difficult (Capcarrere 2002). The difficulty of the task has led many researchers to use techniques from evolutionary computing (Mitchell et a., 1993; Packard 1988; Richards et al., 1990). Starting with randomly generated rules, evolutionary algorithms have evolved methods to resolve the density classification and two cell synchronization tasks and to synchronize groups of cells (Crutchfield and Mitchell 1995; Crutchfield et al., 2003; Das et al., 1995; Umeo et al., 20021994).