A Basis for Universality?

The existence of four classes of cellular automata was presented above as a largely empirical result. Techniques from computation theory may provide a basis, and ultimately a proof, of this result.

The first crucial observation is that with special initial states one cellular automaton may behave just like another. In this way one cellular automaton may be considered to ``simulate'' another. A single site with a particular value in one cellular automaton may be simulated by a fixed block of sites in another; after a fixed number of time steps, the evolution of these blocks imitates the single time-step evolution of sites in the first cellular automaton. For example, sites with value 0 and 1 in the first cellular automaton may be simulated by blocks of sites 00 and 11, respectively, in the second cellular automaton, and two time steps of evolution in the second cellular automaton correspond to one time step in the first. Then, with a special initial state containing 11 and 00 but not 01 and 10 blocks, the second cellular automaton may simulate the first.

Figure 14 gives the network that represents the simulation capabilities of symmetric cellular automata with and . (Only simulations involving blocks of length less than four sites were included in the construction of the network.) If a cellular automaton is computationally universal, then with a sufficiently long encoding it should be able to simulate any other cellular automaton, so that a path should exist from the node that represents its rule to nodes representing all other possible rules.

An example of the simulation of one cellular automaton by another is the simulation of the additive rule 90 (Eq. 1) by the class 3 rule 18. A rule 18 cellular automaton behaves exactly like a rule 90 cellular automaton if alternate sites in the initial configuration have value 0 (so that 0 and 1 in rule 90 are represented by 00 and 01 in rule 18) and alternate time steps are considered. Figure 15 shows evolution according to rule 18 from a disordered initial state. Two ``phases'' are clearly evident: one in which sites at even-numbered positions have value 0 and one in which sites at odd-numbered positions have value 0. The boundaries between these regions execute approximately random walks and eventually annihilate in pairs, leaving a system consisting of blocks of sites that evolve according to the additive rule 90. (Cf. P. Grassberger, ``Chaos and Diffusion in Deterministic Cellular Automata,'' to be published in Physica D.) Thus the simulation of rule 90 by rule 18 may be considered an ``attractive'' one: starting from almost all initial states, rule 18 evolves toward states in which it simulates rule 90. In general, one expects that some paths in the network of Fig. 14 are attractive, while the rest are repulsive. The consequences of a repulsive simulation path are illustrated in Fig. 16: with special initial states rule 94 behaves like rule 90, but any impurities in the initial states grow and eventually dominate the evolution of the system.

[ Figure 14 ] Simulation network for symmetric cellular automaton rules with and . Each rule is specified by the number obtained as shown in Fig. 7, and its behavior class is indicated by shades of gray: light gray corresponds to class 1, medium gray to class 2, and dark gray to class 3. Rule A is considered to simulate rule B if there exist blocks of site values that evolve under rule A as single sites would evolve under rule B. Simulations are included in the network shown only when the necessary blocks are three or fewer sites long. Rules 90 and 150 are additive class 3 rules, rule 204 is the identity rule, and rules 170 and 240 are left- and right-shift rules, respectively. Attractive simulation paths are indicated by bold lines. (Network courtesy of J. Milnor.)

[ Figure 15 ] Evolution of the class 3 cellular automaton rule 18 from a disordered initial state with pairs of sites combined. The pair of site values 00 are shown as black, 01 as red, 10 as green, and 11 as blue. At large times two phases are clearly evident, separated by ``defects'' that execute approximately random walks and ultimately annihilate in pairs. In each phase alternate sites have value 0, and the other sites evolve according to the additive rule 90. Thus for almost all initial states rule 18 behaves like rule 90 at large times. Rule 18 therefore follows an attractive simulation path to rule 90.

[ Figure 16 ] Evolution of the class 2 cellular automaton rule 94 from an initial state in which the members of most pairs of sites have the same values, so that the digrams 00 and 11 predominate and the sequences 010 and 101 are nearly absent. (Color designations are the same as in Fig. 15.) Class 3 behavior occurs, but is unstable: class 2 behavior is ``seeded'' by 10 and 01 digrams and ultimately dominates. Rule 94 exhibits a repulsive simulation path to the class 3 additive rule 90 and an attractive path to the identity rule 204.

Class 1 cellular automata have an attractive simulation path to rule 0 (or its equivalents). Class 2 cellular automata have attractive simulation paths to the identity rule 204. A conjecture for which some evidence exists is that all class 3 rules exhibit attractive simulations to additive rules such as 90 or 150. Simulation by blocking of site values is analogous to a block spin or renormalization group transformation; additive rules have the special property that they are invariant under such transformations. As mentioned earlier, class 4 cellular automata are distinguished by the presence of simulation paths leading to every other cellular automaton rule. It is likely that no specific path is distinguished as attractive.

Cellular automata of different classes may thus be distinguished by their limiting behavior under simulation transformations. This approach suggests that classification of the qualitative behavior of cellular automata may be related to determinations of equivalence of systems and problem classes in computation theory. In general, one may hope for fundamental connections between computation theory and the theory of complex nonequilibrium statistical systems. Information theory forms a mathematical basis for equilibrium statistical mechanics. Computation theory, which addresses time-dependent processes, may be expected to play a fundamental role in nonequilibrium statistical mechanics.

previous  l  next