|
Articles Cellular Automata Statistical Mechanics of Cellular Automata (1983)
Statistical Mechanics of Cellular Automata (1983) |
|
Section 3 analyzed the behavior of cellular automata by considering the statistical properties of the set of values of sites in individual cellular automaton configurations. The alternative approach taken in this section considers the statistical properties of the set (ensemble) comprising all possible complete configurations of a cellular automaton (in analogy with the 
-space approach to classical statistical mechanics). Such an approach provides connections with dynamical systems theory (Ott, 1981) and the formal theory of computation (Minsky, 1967; Arbib, 1969; Manna, 1974; Hopcroft and Ullman, 1979; Beckman, 1980), and yields a view of self-organization phenomena complementary to that developed in Sec. 3. Cellular automaton rules may be considered as a form of ``symbolic dynamics'' (e.g., Alekseev and Yakobson, 1981), in which the degrees of freedom in the system are genuinely discrete, rather than being continuous but assigned to discrete ``bins.''
As in Sec. 3, we examine here only elementary cellular automata. Some results on global properties of more complicated cellular automata will be mentioned in Sec. 5.
For most of this section, it will be convenient to consider ``finite'' cellular automata, containing only a finite number of sites 
. There are a total of 
possible configurations for such a cellular automaton. Each configuration is uniquely specified by a length binary integer whose digits give the values of the corresponding sites. (9) (A configuration of an infinite cellular automaton would correspond to a binary real number.) The evolution of a finite cellular automaton depends on the boundary conditions applied. We shall usually assume periodic boundary conditions, in which the first and last sites are identified, as if the sites lay on a circle of circumference . One could alternatively take an infinite sequence of sites, but assume that all those outside the region of length have value 0. Results obtained with these two choices were compared in Fig. 9, and no important qualitative differences were found. Most of the results derived in this section are also insensitive to the form of boundary conditions assumed. However, several of the later ones depend sensitively on the value of taken.
Cellular automaton rules define a transformation from one sequence of binary digits to another. The rules thus provide a mapping from the set of binary numbers of length onto itself. For the trivial case of rule 0, all binary numbers are mapped to zero. Figure 19 shows the mappings corresponding to evolution for one and five time steps according to cellular automaton rule 90 with 
. The mapping corresponding to one time step is seen to maintain some nearby sets of configurations. After five time steps, however, the evolution is seen to map configurations roughly uniformly, so that the final configurations obtained from nearby initial configurations are essentially uncorrelated.
time steps according to the modulo-two rule 90. Each possible configuration is represented by the decimal equivalent of the binary number whose digits give the values at each of its sites. The horizontal axis gives the number specifying the initial configuration; the vertical axes that for the final configuration. Each initial configuration is mapped to a unique final configuration.A convenient measure of distance in the space of cellular automaton configurations is the ``Hamming distance'' 
[familiar from the theory of error-correcting codes (Peterson and Weldon, 1972)], defined as the number of digits (bits) which differ between the binary sequences 
and 
. [Thus in Boolean form, 
.] Particular configurations correspond to points in the space of all possible configurations. Under cellular automaton evolution, each initial configuration traces out a trajectory in time. If cellular automaton evolution is ``stochastic,'' then the trajectories of nearby points (configurations) must diverge (exponentially) with time. Consider first the case of two initial configurations (say, 
and 
) which differ by a change in the value at one site (and are thus separated by unit Hamming distance). After 
time steps of cellular automaton evolution, this initial difference may affect the values of at most 
sites (so that 
). However, for simple cellular automaton rules, the difference remains localized to a few sites, and the total Hamming distance tends rapidly to a small constant value. The behavior for complex cellular automaton rules differs radically between additive rules (such as 90 and 150) and nonadditive ones. For additive rules, the difference obtained after time steps is given simply by the evolution of the initial difference (in this case a single nonzero site) for time steps. The Hamming distance at time step is thus given by the number of nonzero sites in the configuration obtained by evolution from a single site, and for rule 90 has the form 
, as illustrated in Fig. 20(a). The average Hamming distance, smoothed over many time steps, behaves as 
. For nonadditive rules, the difference between configurations obtained through cellular automaton evolution no longer depends only on the difference between the initial configurations. Figure 20(c) shows the difference between configurations obtained by evolution according to the nonadditive cellular automaton rule 126. The lack of symmetry in the pattern is a reflection of the dependence on the values of multiple initial sites. Figure 20(b) shows the Hamming distance corresponding to this difference. Apart from small fluctuations, it is seen to increase linearly with , tending at large to the form 
. This Hamming distance is the same as would be obtained by comparing sequences of sites in two disordered configurations with density 0.5. Thus a change in the value of a small number of initial sites is amplified by the evolution of a nonadditive cellular automaton, and leads to configurations with a linearly increasing number of essentially uncorrelated sites. (Changes in single sites may sometimes be eradicated after a single time step; this exceptional behavior occurs for cellular automaton rule 18, but is always absent if more than one adjacent site is reversed.) A bundle of initial trajectories therefore diverges with time into an exponentially increasing volume.
between two configurations is defined as the number of bits (site values) which differ between the configurations. (a) shows the evolution of the Hamming distance between two configurations of the additive cellular automaton 90 (modulo-two rule); (b) shows the corresponding Hamming distance for the nonadditive cellular automaton 126; and (c) gives the actual difference (modulo two) between the configurations of cellular automaton 126 for the first few time steps. For nonadditive rules [case (b)], 
, while for additive rules [case (a)], after time averaging, 
.One may specify a statistical ensemble of states for a finite cellular automaton by giving the probability for each of the possible configurations. In a collection of many disordered states with density 
, each possible cellular automaton configuration is asymptotically populated with equal probability. Such a collection of states will be termed an ``equiprobable ensemble,'' and may be considered ``completely disorganized.'' Cellular automaton evolution modifies the probabilities for states in an ensemble, thereby generating ``organization.'' Figure 21 shows the probabilities for the 1024 possible configurations of a finite cellular automaton with 
obtained after evolution for ten time steps according to rule 126 from an initial equiprobable ensemble. Figure 22 shows the evolution of these probabilities over ten time steps for several complex cellular automata. At each time step, dots are placed in positions corresponding to configurations occurring with nonzero probabilities. At 
, all configurations are taken to be equally probable. Cellular automaton evolution modifies the probabilities for different configurations, reducing the probabilities for some to zero, and leading to ``gaps'' in Fig. 22. In the initial ensemble, all configurations were assigned equal a priori probabilities. After evolution (or ``processing'') for a few time steps, an equilibrium ensemble is attained in which different configurations carry different probabilities, according to a definite distribution. Properties of the more probable configurations dominate statistical averages over the ensemble, giving rise to the distinctive average local features of equilibrium configurations described in Sec. 3.
obtained by evolution according to rule 126 for ten time steps from an initial ensemble containing each possible configuration with equal probability. On the horizontal axis, each configuration 
is labeled by a ten-digit binary integer (marked in decimal form) whose digits give the values of the corresponding sites. The null configuration (with value zero at all sites) is labeled by the integer 0, and occurs with the largest probability 
. The inequality of the probabilities for initially equiprobable configurations is a reflection for self-organization.
In the limit 
, a cellular automaton configuration may be specified by real number in the interval 0 to 1 whose binary decomposition consists of a sequence of digits corresponding to the values of the cellular automaton sites. Then the equilibrium ensemble of cellular automaton configurations analogous to those of Fig. 22 corresponds to a set of points on the real line. The unequal probabilities for appearance of 0 and 1 digits, together with higher-order correlations, implies that the points form a Cantor set (Farmer, 1982a, 1982b). The fractal dimensionality of the Cantor set is given by the negative of the entropy discussed below, associated with the ensemble of cellular automaton configurations (and hence real-number binary digit sequences) (Farmer, 1982a, 1982b). For rule 126 the fractal dimension of the Cantor set is then 0.5.
An important feature of the elementary cellular automata considered here and in Sec. 3 is their ``local irreversibility.'' Cellular automaton rules may transform several different initial configurations into the same final configuration. A particular configuration thus has unique descendents, but does not necessarily have unique ancestors (predecessors). Hence the trajectories traced out by the time evolution of several cellular automaton configurations may coalesce, but may never split. A trivial example is provided by cellular automaton rule 0, under which all possible initial configurations evolve after one time step to the unique null configuration. In a reversible system, each state has a unique descendent and a unique ancestor, so that trajectories representing time evolution of different states may never intersect or meet. Thus in a reversible system, the total number of possible configurations must remain constant with time (Liouville's theorem). However, in an irreversible system, the number of possible configurations may decrease with time. This effect is responsible for the ``thinning'' phenomenon visible in Fig. 22. The trajectories corresponding to the evolution of cellular automaton configurations are found to become concentrated in limited regions, and do not asymptotically fill the available volume densely and uniformly. This behavior makes self-organization possible, by allowing some configurations to occur with larger probabilities than others even in the large-time equilibrium limit.
One consequence of local irreversibility evident from Fig. 22 is that some cellular automaton configurations may appear as initial conditions but may never be reached as descendents of other configurations through cellular automaton time evolution. (10) Such configurations carry zero weight in the ensemble obtained by cellular automaton evolution. In the trivial case of cellular automaton rule 0, only the null state with all sites zero may be reached by time evolution; all other configurations are unreachable. Rule 4 generates only those configurations in which no two adjacent sites have the same value. The fraction of the possible configurations which satisfy this criterion tends to zero as tends to infinity, so that in this limit, a vanishingly small fraction of the configurations are reached. Cellular automaton rule 204 is an identity transformation, and is unique among cellular automaton rules in allowing all configurations to be reached. (The rule is trivially reversible.) Assuming periodic boundary conditions, one finds that with odd, the complex additive rule 90 generates only configurations in which an even number of sites have value one, and thus allows exactly half of the possible configurations to be reached. For even 
, 
of the possible configurations may be reached. A finite fraction of all the configurations are thus reached in the limit . For the complex nonadditive rule 126, inspection of Fig. 8 shows that only configurations in which nonzero sites appear in pairs may be reached. Figure 23 shows the fraction of unreachable configuration for this cellular automaton rule as a function of . The fraction tends steadily to one as . A complete characterization of the unreachable configurations for this case is given in Martin et al. (1983); these configurations are enumerated there, and their fraction is shown to behave as 
for large , where 
is determined as the root of a cubic equation. Similar behavior is found for other nonadditive rules.
Irreversible behavior in cellular automata may be analyzed by considering the behavior of their ``entropy'' 
or ``information content'' 
. Entropy is defined as usual as the logarithm (here taken to base two) of the average number of possible states of a system, or
where 
is the probability for state 
. The entropy may equivalently be considered as the average number of binary bits necessary to specify one state in an ensemble of possible states. The total entropy of a system is the sum of the entropies of statistically independent subsystems. Entropy is typically maximized when a system is completely disorganized, and the maximum number of subsystems act independently. The entropy of a cellular automaton takes on its maximal value of one bit per site for an equiprobable ensemble. For reversible systems, time evolution almost always leads to an increase in entropy. However, for irreversible systems, such as cellular automata, the entropy may decrease with time. Figure 24 shows the time dependence of the entropy for a finite cellular automaton with , evolving according to rule 126, starting from an initial equiprobable ensemble. The entropy is seen to decrease with time, eventually reaching a constant equilibrium value. The decrease is a direct signal of irreversibility.
possible configurations of a length cellular automaton (with periodic boundary conditions) not reached by evolution from an arbitrary initial configuration according to cellular automaton rule 126. The existence of unreachable configurations is a consequence of the irreversibility of cellular automaton evolution. The fraction of such configurations is seen to increase steadily towards one as increases.
evolving according to rule 126 from an initial equiprobable ensemble. The entropy gives the logarithm of the average number of possible configurations. Its decrease with time is a reflection of the local irreversibility of the cellular automaton.The entropy for a finite cellular automaton given in Fig. 24 is obtained directly from Eq. (4.1) by evaluating the probabilities for each of the finite set of possible configurations. For infinite cellular automata, enumeration of all configurations is no longer possible. However, so long as values of sufficiently separated sites are statistically independent, the average entropy per site may nevertheless be estimated by a limiting procedure. Define a ``block entropy'' [or ``Renyi entropy'' (Renyi, 1970; Farmer, 1982a, 1982b)]
where 
denotes the probability for a sequence of 
values in an infinite cellular automaton configuration. The limit 
gives the average total entropy per site. This limit is approached rapidly for almost all cellular automaton configurations, reflecting the exponential decrease of correlations with distance discussed in Sec. 3. [Similar results are obtained in estimating the entropy of printed English from single letter, digram, trigram and so on frequencies (Shannon 1951). Typical results (for example, for the text of this paper) are 
, 
, 
, and 
.]
Irreversibility is not a necessary feature of cellular automata. In the case of the elementary cellular automata considered here, the irreversibility results from the assumption that a configuration 
at a particular time step 
depends only on its immediate predecessor so that its evolution may be represented schematically by 
. Except in the trivial case of the identity transformation (rule 204), 
is not invertible. The cellular automata are discrete analogs of systems governed by partial differential equations of first order in time (such as the diffusion equation), and exhibit the same local irreversibility. One may construct reversible one-dimensional cellular automata (Fredkin, 1982; Margolus, 1982) by allowing a particular configuration to depend on the previous two configurations, in analogy with reversible second-order differential equations such as the wave equation. The evolution of these cellular automata may be represented schematically by 
. (11)
The invertibility of modulo-two addition allows 
to be obtained uniquely from and 
, so that all pairs of successive configurations have unique descendants and unique ancestors. For infinite reversible cellular automata, the entropy (4.1) (evaluated for the appropriate successive pairs of configurations) almost always increases with time. Finite reversible cellular automata may exhibit globally irreversible behavior when dissipative boundary conditions are imposed. Such boundary conditions are obtained if sites beyond the boundary take on random values at each time step. If all sites beyond the boundary have a fixed or predictable value as a function of time, the system remains effectively reversible. With simple initial configurations, reversible cellular automata generate self-similar patterns analogous to those found for irreversible ones. (12) A striking difference is that reversible rules yield diamond-shaped structures symmetrical in time, rather than the asymmetrical triangle structures found with irreversible rules.
Since a finite cellular automaton has a total of only possible configurations, the sequence of configurations reached by evolution from any initial configuration must become periodic after at most time steps (the ``Poincare recurrence time''). After an initial transient, the cellular automaton must enter a cycle in which a set of configurations is generated repeatedly, as illustrated in Fig. 25. Figure 8 suggests that simple cellular automata yield short cycles containing only a few configurations, while complex cellular automata may yield much longer cycles. Simple rules such as 0 or 72 evolve after a fixed small number of time steps from any configuration to the stationary null configuration, corresponding to a trivial length-one cycle. Other simple cellular automaton rules, such as 36, 76, or 104 evolve after 
time steps to nontrivial stationary configurations (with cycle length one). Rules such as 94 or 108 yield (after a transient of steps) a state consisting of a set of small independent regions, each of which independently follows a short cycle (usually of length one or two and at most of length 
, where is the number of sites in the region). In general, simple cellular automata evolve to cycles whose length remains constant as increases. On the other hand, complex cellular automata may yield cycles whose length increases without bound as increases. Figure 26 shows the distribution in the number of time steps before evolution from each possible initial configuration according to the complex rule 126 leads to repetition of a configuration. Only a small fraction of the possible configurations is seen to be reached in evolution from a particular initial configuration. For example, in the case 
, a maximum of eight distinct configurations (out of 256) are generated by evolution from any specific initial state. After a transient of at most two time steps, the cellular automaton enters a cycle, which repeats after at most six further time steps. Apart from the trivial one-cycle corresponding to the null configuration, six distinct cycles (containing nonintersecting sets of configurations) occur. Four have length six, and two have length two. A total of 29 distinct ``final'' configurations appear in these cycles. The number of configurations reached by evolution from a particular initial state increases with as shown in Fig. 26. For , the maximum is 38 states, while for 
, it is at least 1547. Similar behavior is found for most other complex nonadditive rules.
(and periodic boundary conditions) according to rule 126. Evolution from a particular initial state could generate up to 
distinct configurations before entering a cycle and returning to a configuration already visited. Much shorter cycles, however, are seen to occur in practice.Analytical results for transient and cycle lengths may be given for finite cellular automata (with periodic boundary conditions) evolving according to the additive rules 90 and 150 (Martin et al. 1983). A complete and general derivation may be obtained using algebraic methods and is given in Martin et al. (1983). The additive superposition principle implies that the evolution of any initial configuration is a superposition of evolution from single nonzero sites (in each of the cyclically equivalent possible positions). The period of any cycle must therefore divide the period 
obtained by evolution from a single nonzero site. Similarly, the length of any transient must divide the length 
obtained with a single nonzero initial site. It is found that is identical for rules 90 and 150, but in general differs. The first few values of for rules 90 and 150 (for 
through 
) are 1, 1, 3, 2, 7, 1, 7, 6, 31, 4, 63, 14, 15, 1, 15, 14, 511, 12, 63, 62, 2047, 8, 1023, 126, 511, 28, 16383, and 30. Consider rule 90; derivations for rule 150 are similar. Whenever is of the form 
, the cellular automaton ultimately evolves from any initial configuration to the null configuration, so that 
in this case. When is odd, it is found that the first configuration in the cycle always consists of two nonzero sites, separated by a single zero site. The nonzero sites may be taken at positions 
modulo . Equation (3.2) implies that configurations obtained by evolution for 
time steps again contain exactly two nonzero sites, at positions 
modulo . A cycle occurs when 
. 
then divides 
given by 
where 
is defined as the minimum 
for which 
, and 
or 
. The multiplicative order function 
(e.g., MacWilliams and Sloane, 1977) is defined as the minimum for which 
. It is found in fact that 
for most ; the first exception occurs for 
, in which case 
. For 
, 
, so that when 
, 
. Similarly, when 
, 
so that 
and 
, yielding 
for 
. In general, if 
where the are primes not equal to 
, 
. 
divides the Euler totient function 
, defined as the number of integers less than which are relatively prime to (e.g., Apostol, 1976; Hardy and Wright, 1979, Sec. 5.5). [ is even for all 
.] satisfies the Euler-Fermat relation 
. It is clear that 
, where 
denotes the number of primes less than , and the upper bound is saturated when is prime. If is even, then 
, while for odd, 
. Thus 
, where the bound is saturated for some prime . Such a is the maximum possible cycle length for configurations with reflection symmetry, but is approximately the square root of the maximum possible length 
for an arbitrary system with binary sites. (13) When is even, 
. Notice that is an irregular function of : its value depends not only on the magnitude of , but also on its number theoretical properties.
(with periodic boundary conditions) evolving according to rule 126 to reach a particular configuration for the second time, signaling the presence of a cycle. The cycle times found are much smaller than the value obtained if evolution from a particular initial configuration eventually visited all possible configurations. The results for 
and include all 256 and 1024 possible initial configurations; those for 
and 
are obtained by uniform Monte Carlo sampling from the space of possible initial configurations. In all cases, the number of configurations visited in transients before entering a cycle is very much smaller than the number of configurations in the cycle.When is prime, all possible cycles must have a period of one or exactly . When is composite, any of its divisors may occur as a cycle period. Thus, for example, with , 
, and in evolution from the 
possible non-null initial configurations, forty distinct cycles of length 6 appear, and five of length 3. In general it appears that for large , an overwhelming fraction of cycles have the maximal length .
As mentioned above, for the additive rules 90 and 150, the length of the transients before a cycle is entered in evolution from an arbitrary initial configuration must divide , the length of transient with a single nonzero initial site. For rule 90, 
for odd, and 
otherwise, where 
is the largest which divides . For rule 150, 
if is not a multiple of three, if is odd, and 
otherwise. Since, as discussed above, evolution from all possible initial configurations according to rule 90 visits 
configurations for odd , the result implies that in this case, exactly half of the possible configurations appear on cycles.
Configurations in cellular automata may be divided into essentially three classes according to the circumstances under which they may be generated. One class discussed above consists of configurations which can appear only as initial states, but can never be generated in the course of cellular automaton evolution. A second class contains configurations which cannot arise except within the first, say , time steps. For 
, such configurations have ``parents'' but no ``grandparents.'' The third class of configurations is those which appear in cycles, and may be visited repeatedly. Such configurations may be generated at any time step (for example, by choosing an initial configuration at the appropriate point in the cycle, and then allowing the necessary number of cycle steps to occur). The second class of configurations appears as transients leading to cycles. The cycles may be considered as attractors eventually attained in evolution from any initial configuration. The possible configurations of a finite cellular automaton may be represented as nodes in a graph, joined by arcs representing transitions corresponding to cellular automaton evolution. Cycles in the graph correspond to cycles in cellular automaton evolution. As shown in Martin et al. (1983), the transient configurations for the additive rules 90 and 150 appear on balanced quaternary trees, rooted on the cycles. The leaves of the trees correspond to unreachable configurations. The height of the trees is given by . The balanced structure of the trees implies that the number of configurations which may appear after time steps decreases as 
; 
configurations appear on cycles and may therefore be generated at arbitrarily large times.
The algebraic techniques of Martin et al. (1983) apply only to additive rules. For nonadditive cellular automaton rules, the periods of arbitrary cycles do not necessarily divide the periods of cycles generated by evolution from configurations with one nonzero site. Empirical investigations nevertheless reveal many regularities.
Cyclic behavior is inevitable for finite cellular automata which allow only a finite number of possible states. Infinite cellular automata exhibit finite cycles only under exceptional circumstances. For a wide class of initial states, simple cellular automaton rules can yield nontrivial cyclic behavior. Cycles occur in complex cellular automata only with exceptional initial conditions. Any initial configuration with a finite number of nonzero sites either evolves ultimately to the null state, or yields a pattern whose size increases progressively with time. Most infinite initial configurations do not lead to cyclic behavior. However, if the values of the initial sites form an infinite periodic sequence (cf. Miller, 1970, 1980), with period , then the evolution of the infinite cellular automaton will be identical to that of a finite cellular automaton with 
, and cycles with length 
will be found.
The transformation of a finite cellular automaton configuration according to cellular automaton rules defines a mapping in the set of binary integers representing the cellular automaton configurations. An example of such a mapping was given in Fig. 19. Repeated applications of the mapping yield successive time steps in the evolution of the cellular automaton. One may compare the results with those obtained for a system which evolves by iteration of a random mapping among the integers (cf. Kauffman, 1969). Random mappings of 
elements are obtained by choosing one of the possible images independently for each integer and with equal probabilities. The mapping is permitted to take an element to itself. In this way, all 
possible mappings are generated with equal probability. The probability of a particular element's having no preimage (predecessor) under a random mapping between elements is 
. In the limit 
this implies that a fraction 
of the possible states are not reached in evolution by iteration of a random mapping. For complex nonadditive cellular automata, it appears that as , almost all configurations become unreachable, indicating that cellular automaton evolution is ``more irreversible'' than iteration of a random mapping would imply. A system evolving according to a random mapping exhibits cycles analogous to those found in actual cellular automata. The probability of a length 
cycle's occurring by iteration of a mapping between elements is found to be
(Harris, 1960; Knuth, 1981, Sec. 3.1, Ex. 6, 11-16; Levy, 1982). Cycles of the maximum length occur with finite probability. In the large limit, the average cycle length becomes 
, while the standard deviation of the cycle length distribution is 
. The length of transients follows exactly the same distribution. The number of distinct cycles 
. If we take 
for comparison with an cellular automaton, this implies an average cycle length 
, an average transient length , 
unreachable configurations, and 
distinct cycles. Cellular automaton rule 126 yields in this case an average cycle length 
, an average transient length 
, 190 unreachable configurations, and 7 distinct cycles. Any agreement with results for random mappings appears to be largely fortuitous: even for large cellular automata do not behave like random mappings.
This section has thus far considered cellular automata which evolve according to definite deterministic local rules. However, as discussed in Sec. 3, one may introduce probabilistic elements or noise into cellular automata rules---for example, by reversing the value of a site at each time step with probability 
. Section 3 showed that the local properties of cellular automata change continuously as is increased from zero. Global properties may, however, change discontinuously when a nonzero is introduced. An example of such behavior is shown in Fig. 27, which gives the fraction of configurations visited as a function of time for a cellular automaton evolving according to rule 126 with various values of , starting from a single typical initial configuration. When 
, only six distinct configurations are generated before the cellular automaton enters a cycle. When 
, the cellular automaton ultimately visits every possible configuration (cf. Gach et al., 1978). For 
, one may approximate each configuration as being chosen from the possible configurations with equal probabilities: in this case, the average number of configurations visited after time steps is found to be 
.
time steps in a finite cellular automaton (with 
) evolving from a single typical initial state according to rule 126 in the presence of noise which randomly reverses the values of sites at each time step with probability 
. When 
, the cellular automaton enters a cycle after visiting only six distinct configurations. When 
, the cellular automaton eventually visits all 128 possible configurations.Cellular automata may be viewed as simple idealizations of physical systems. They may also be interpreted as ``computers'' (von Neumann, 1966; Baer and Martinez, 1974; Burks, 1970; Aladyev, 1974, 1976; Toffoli, 1977b) and analyzed using methods from the formal theory of computation (Minsky, 1967; Arbib, 1969; Manna, 1974; Hopcroft and Ullman, 1979; Beckman, 1980). With this interpretation, the initial configuration of a cellular automaton represents a ``program'' and ``initial data,'' processed by cellular automaton time evolution to give a configuration corresponding to the ``output'' or ``result'' of the ``computation.'' The cellular automaton rules represent the basic mechanism of the computer; different programs may be ``run'' (or different ``functions evaluated'') by giving different initial or ``input'' configurations. This process is analogous to the ``evolution'' of the sequence of symbols on the tape of a Turing machine (Turing, 1936). However, instead of considering a single ``head'' which modifies one square of the tape at each time step, the cellular automaton evolution simultaneously affects all sites at each time step. As discussed in Sec. 5, there exist ``universal'' cellular automata analogous to universal Turing machines, for which changes in the initial configuration alone allow any computable (or ``recursive'') function to be evaluated. A universal Turing machine may simulate any other Turing machine using an ``interpreter program'' which describes the machine to be simulated. Each ``instruction'' of the simulated machine is simulated by running the appropriate part of the interpreter program on the universal machine. Universal cellular automata may similarly simulate any other cellular automata. The interpreter consists of an encoding of the configurations for the cellular automaton to be simulated on the universal automaton. A crucial point is that so long as the encoding defined by the interpreter is sufficiently simple, the statistical characteristics of the evolution of configurations in the universal cellular automaton will be shared by the cellular automaton being simulated. This fact potentially forms the basis for universality in the statistical properties of complicated cellular automata.
The simplest encodings which allow one cellular automaton to represent or simulate others are pure substitution or ``linear'' ones, under which the value of a single site is represented by a definite sequence of site values. (Such encodings are analogous to the correspondences between complex cellular automaton rules mentioned in Sec. 3.) For example, a cellular automaton 
evolving according to rule 22 may be used to simulate another cellular automaton 
evolving according to rule 146. For every 0 in the initial configuration of , a sequence 00 is taken in the initial configuration of , and for every 1 in , 01 is taken in . Then after time steps, the configuration of A under this encoding is identical to that obtained by evolution of B for time steps. If cellular automaton B instead evolved according to rule 182, 01 (or 10) in A would correspond to 0 in B, and 00 to 1. The simplicity of the interpreter necessary to represent rules 146 and 182 under rule 22 is presumably responsible for the similarities in their statistical behavior found in Sec. 3. Figure 28 gives a network which describes the simulation capabilities of the complex elementary cellular automaton rules using length two linear encodings and with the simulated rule running at half the speed of the simulator. Many of these complex rules may also simulate simple rules under such an encoding. Simulations possible with longer linear encodings appear to be described by indirection through the network. Not all complex cellular automaton rules are thus related by linear encodings of any length.
As discussed in Sec. 5, the elementary cellular automata considered here and in Secs. 2 and 3 are not of sufficient complexity to be capable of universal computation. However, some of the more complicated cellular automata described in Sec. 5 are ``universal,'' and may therefore in principle represent any other cellular automata. The necessary encoding must be of finite length, but may be very long. The shorter or simpler the encoding, the closer will be the statistical properties of the simulating and simulated cellular automata.
