## 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.

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.