|
Articles Cellular Automata Statistical Mechanics of Cellular Automata (1983)
Statistical Mechanics of Cellular Automata (1983) |
|
Cellular automata are mathematical idealizations of physical systems in which space and time are discrete, and physical quantities take on a finite set of discrete values. A cellular automaton consists of a regular uniform lattice (or ``array''), usually infinite in extent, with a discrete variable at each site (``cell''). The state of a cellular automaton is completely specified by the values of the variables at each site. A cellular automaton evolves in discrete time steps, with the value of the variable at one site being affected by the values of variables at sites in its ``neighborhood'' on the previous time step. The neighborhood of a site is typically taken to be the site itself and all immediately adjacent sites. The variables at each site are updated simultaneously (``synchronously''), based on the values of the variables in their neighborhood at the preceding time step, and according to a definite set of ``local rules.''
Cellular automata were originally introduced by von Neumann and Ulam (under the name of ``cellular spaces'') as a possible idealization of biological systems (von Neumann, 1963, 1966), with the particular purpose of modelling biological self-reproduction. They have been applied and reintroduced for a wide variety of purposes, and referred to by a variety of names, including ``tessellation automata,'' ``homogeneous structures,'' ``cellular structures,'' ``tessellation structures,'' and ``iterative arrays.''
Physical systems containing many discrete elements with local interactions are often conveniently modelled as cellular automata. Any physical system satisfying differential equations may be approximated as a cellular automaton by introducing finite differences and discrete variables. (1) Nontrivial cellular automata are obtained whenever the dependence on the values at each site is nonlinear, as when the system exhibits some form of ``growth inhibition.'' A very wide variety of examples may be considered; only a few are sketched here. In the most direct cases, the cellular automaton lattice is in position space. At a microscopic level, the sites may represent points in a crystal lattice, with values given by some quantized observable (such as spin component) or corresponding to the types of atoms or units. The dynamical Ising model (with kinetic energy terms included) and other lattice spin systems are simple cellular automata, made nondeterministic by ``noise'' in the local rules at finite temperature. At a more macroscopic level, each site in a cellular automaton may represent a region containing many molecules (with a scale size perhaps given by an appropriate correlation length), and its value may label one of several discrete possible phases or compositions. In this way, cellular automata may be used as discrete models for nonlinear chemical systems involving a network of reactions coupled with spatial diffusion (Greenberg et al., 1978). They have also been used in a (controversial) model for the evolution of spiral galaxies (Gerola and Seiden, 1978; Schewe, 1981). Similarly, they may provide models for kinetic aspects of phase transitions (e.g., Harvey et al., 1982). For example, it is possible that growth of dendritic crystals (Langer, 1980) may be described by aggregation of discrete ``packets'' with a local growth inhibition effect associated with local releases of latent heat, and thereby treated as a cellular automaton [Witten and Sander (1981) discuss a probabilistic model of this kind, but there are indications that the probabilistic elements are inessential]. The spatial structure of turbulent fluids may perhaps be modelled using cellular automata by approximating the velocity field as a lattice of cells, each containing one or no eddies, with interactions between neighboring cells. Physical systems may also potentially be described by cellular automata in wave-vector or momentum space, with site values representing excitations in the corresponding modes.
Many biological systems have been modelled by cellular automata (Lindenmayer, 1968; Herman, 1969; Ulam, 1974; Kitagawa, 1974; Baer and Martinez, 1974; Rosen, 1981) (cf. Barricelli, 1972). The development of structure and patterns in the growth of organisms often appears to be governed by very simple local rules (Thompson, 1961; Stevens, 1974) and is therefore potentially well described by a cellular automaton model. The discrete values at each site typically label types of living cells, approximated as growing on a regular spatial lattice. Short-range or contact interactions may lead to expression of different genetic characteristics, and determine the cell type. Simple nonlinear rules may lead to the formation of complex patterns, as evident in many plants and animals. Examples include leaf and branch arrangements (e.g., Stevens, 1974) and forms of radiolarian skeletons (e.g., Thompson, 1961). Simple behavior and functioning of organisms may be modelled by cellular automata with site values representing states of living cells or groups of cells [Burks (1973) and Flanigan (1965) discuss an example in heart fibrillation]. The precise mathematical formulation of such models allows the behavior possible in organisms or systems with particular construction or complexity to be investigated and characterized (e.g., von Neumann, 1966). Cellular automata may also describe populations of nonmobile organisms (such as plants), with site values corresponding to the presence or absence of individuals (perhaps of various types) at each lattice point, with local ecological interactions.
Cellular automata have also been used to study problems in number theory and their applications to tapestry design (Miller, 1970, 1980; ApSimon, 1970a, 1970b; Sutton, 1981). In a typical case, successive differences in a sequence of numbers (such as primes) reduced with a small modulus are taken, and the geometry of zero regions is investigated.
As will be discussed in Sec. 4, cellular automata may be considered as parallel processing computers (cf. Manning, 1977; Preston et al., 1979). As such, they have been used, for example, as highly parallel multipliers (Atrubin, 1965; Cole, 1969), sorters (Nishio, 1981), and prime number sieves (Fischer, 1965). Particularly in two dimensions, cellular automata have been used extensively for image processing and visual pattern recognition (Deutsch, 1972; Sternberg, 1980; Rosenfeld, 1979). The computational capabilities of cellular automata have been studied extensively (Codd, 1968; Burks, 1970; Banks, 1971; Aladyev, 1974, 1976; Kosaraju, 1974; Toffoli, 1977b), and it has been shown that some cellular automata could be used as general purpose computers, and may therefore be used as general paradigms for parallel computation. Their locality and simplicity might ultimately permit their implementation at a molecular level.
The notorious solitaire computer game ``Life'' (Conway, 1970; Gardner, 1971, 1972; Wainwright, 1971--1973; Wainwright, 1974; Buckingham, 1978; Berlekamp et al., 1982; R. W. Gosper, private communications) (qualitatively similar in some respects to the game of ``Go'') is an example of a two-dimensional cellular automaton, to be discussed briefly in Sec. 5.
Until Sec. 5, we shall consider exclusively one-dimensional cellular automata with two possible values of the variables at each site (``base 2'') and in which the neighborhood of a given site is simply the site itself and the sites immediately adjacent to it on the left and right. We shall call such cellular automata elementary. Figure 1 specifies one particular set of local rules for an elementary cellular automaton. On the top row, all 
possible values of the three variables in the neighborhood are given, and below each one is given the value achieved by the central site on the next time step according to a particular local rule. Figure 2 shows the evolution of a particular state of the cellular automaton through one time step according to the local rule given in Fig. 1.
The local rules for a one-dimensional neighborhood-three cellular automaton are described by an eight-digit binary number, as in the example of Fig. 1. (In specifying cellular automata, we use this binary number interchangeably with its decimal equivalent.) Since any eight-digit binary number specifies a cellular automaton, there are 
possible distinct cellular automaton rules in one dimension with a three-site neighborhood. Two inessential restrictions will usually be imposed on these rules. First, a cellular automaton rule will be considered ``illegal'' unless a ``null'' or ``quiescent'' initial state consisting solely of 0 remains unchanged. This forbids rules whose binary specification ends with a 1 (and removes symmetry in the treatment of 0 and 1 sites). Second, the rules must be reflection symmetric, so that 100 and 001 (and 110 and 011) yield identical values. These restrictions (2) leave 32 possible ``legal'' cellular automaton rules of the form 
.
The local rules for a cellular automaton may be considered as a Boolean function of the sites within the neighborhood. Let 
be the value of site 
at time step 
. As a first example consider the ``modulo-two'' rule 90 (also used as the example for Fig. 1). According to this rule, the value of a particular site is simply the sum modulo two of the values of its two neighboring sites on the previous time step. The Boolean equivalent of this rule is therefore
or schematically 
, where 
denotes addition modulo two (``exclusive disjunction'' or ``inequality''). Similarly, rule 18 is equivalent to 
[where 
denotes 
], rule 22 to 
, rule 54 to 
, rule 150 to 
, and so on. Designations 
and 
always enter symmetrically in legal cellular automaton rules by virtue of reflection symmetry. The Boolean function representation of cellular automaton rules is convenient for practical implementation on standard serial processing digital computers. (3)
Some cellular automaton rules exhibit the important simplifying feature of ``additive superposition'' or ``additivity.'' Evolution according to such rules satisfies the superposition principle
which implies that the configurations obtained by evolution from any initial configuration are given by appropriate combinations of those found in Fig. 3 for evolution from a single nonzero site. Notice that such additivity does not imply linearity in the real number sense of Sec. 1, since the addition is over a finite field. Cellular automata satisfy additive superposition only if their rule is of the form 
with 
. Only rules 0, 90, 150, and 204 are of this form. Rules 0 and 204 are trivial; 0 erases any initial configuration, and 204 maintains any initial configuration unchanged (performing the identity transformation at each time step). Rule 90 is the modulo-two rule discussed above, and takes a particular site to be the sum modulo two of the values of its two neighbors at the previous time step, as in Eq. (2.1). Rule 150 is similar. It takes a particular site to be the sum modulo two of the values of its two neighbors and its own value at the previous time step ().
The additive superposition principle of Eq. (2.2) combines values at different sites by addition modulo two (exclusive disjunction). Combining values instead by conjunction (Boolean multiplication) yields a superposition principle for rules 0, 4, 50, and 254. Combining values by (inclusive) disjunction (Boolean addition) yields a corresponding principle for rules 0, 204, 250, and 254. It is found that no other legal cellular automaton rules satisfy superposition principles with any combining function.
The Boolean representation of cellular automaton rules reveals that some rules are ``peripheral'' in the sense that the value of a particular site depends on the values of its two neighbors at the previous time step, but not on its own previous value. Rules 0, 90, 160, and 250 are of the form 
and exhibit this property.
Having discussed features of possible local rules we now outline their consequences for the evolution of elementary cellular automata. Sections 3 and 4 present more detailed quantitative analysis.
Figure 3 shows the evolution of all 32 possible legal cellular automata from an initial configuration containing a single site with value 1 (analogous to the growth of a ``crystal'' from a microscopic ``seed''). The evolution is shown until a particular configuration appears for the second time (a ``cycle'' is detected), or for at most 20 time steps. Several classes of behavior are evident. In one class, the initial 1 is immediately erased (as in rules 0 and 160), or is maintained unchanged forever (as in rules 4 and 36). Rules of this class are distinguished by the presence of the local rules 
and 
, which prevent any propagation of the initial 1. A second class of rules (exemplified by 50 or 122) copies the 1 to generate a uniform structure which expands by one site in each direction on each time step. These two classes of rules will be termed ``simple.'' A third class of rules, termed ``complex,'' and exemplified by rules 18, 22, and 90, yields nontrivial patterns.
As a consequence of their locality, cellular automaton rules define no intrinsic length scale other than the size of a single site (or of a neighborhood of three sites) and no intrinsic time scale other than the duration of a single time step. The initial state consisting of a single site with value 1 used in Fig. 3 also exhibits no intrinsic scale. The cellular automaton configurations obtained in Fig. 3 should therefore also exhibit no intrinsic scale, at least in the infinite time limit. Simple rules yield a uniform final state, which is manifestly scale invariant. The scale invariance of the configurations generated by complex rules is nontrivial. In the infinite time limit, the configurations are ``self-similar'' in that views of the configuration with different ``magnifications'' (but with the same ``resolution'') are indistinguishable. The configurations thus exhibit the same structure on all scales.
Consider as an example the modulo-two rule 90 (also used as the example for Fig. 1 and in the discussion above). This rule takes each site to be the sum modulo two of its two nearest neighbors on the previous time step. Starting from an initial state containing a single site with value 1, the configuration it yields on successive time steps is thus simply the lines of Pascal's triangle modulo two, as illustrated in Fig. 4 (cf. Wolfram, 1982b). The values of the sites are hence the values of binomial coefficients [or equivalently, coefficients of 
in the expansion of 
] modulo two. In the large time limit, the pattern of sites with value 1 may be obtained by the recursive geometrical construction (cf. Sierpinski, 1916; Abelson and diSessa, 1981, Sec. 2.4) shown in Fig. 5. This geometrical construction manifests the self-similarity (Mandelbrot, 1977, 1982; Geffen et al., 1981) or ``scale invariance'' of the resulting curve. Figure 3 shows that evolution of other complex cellular automata from a single nonzero site yields essentially identical self-similar patterns. An exception is rule 150, for which the value of each site is determined by the sum modulo two of its own value and the values of its two neighbors on the previous time step. The sequence of binary digits obtained by evolution from a single-site initial state for time steps with this rule is thus simply the coefficients of in the expansion of 
modulo two. A geometrical construction for the pattern obtained is given in Fig. 6.
.Figure 7 shows examples of time evolution for some cellular automata with illegal local rules (defined above) which were omitted from Fig. 3. When the quiescence condition is violated, successive time steps involve alternation of 0 and 1 at infinity. When reflection symmetry is violated, the configurations tend to undergo uniform shifting. The self-similar patterns seen in Fig. 3 are also found in cases such as rule 225, but are sheared by the overall shifting. It appears that consideration of illegal as well as ``legal'' cellular automaton rules introduces no qualitatively new features.
[where 
is the golden ratio]. An analogous construction for rule 90 was given in Fig. 5.Figure 3 shows the growth of patterns by cellular automaton evolution from a very simple initial state containing a single nonzero site (seed). Figure 8 now illustrates time evolution from a disordered or ``random'' initial state according to each of the 32 legal cellular automaton rules. A specific ``typical'' initial configuration was taken, with the value of each site chosen independently, with equal probabilities for values 0 and 1. (4) Just as in Fig. 3, several classes of behavior are evident. The simple rules exhibit trivial behavior, either yielding a uniform final state or essentially preserving the form of the initial state. Complex rules once again yield nontrivial behavior. Figure 8 illustrates the remarkable fact that time evolution according to these rules destroys the independence of the initial sites, and generates correlations between values at separated sites. This phenomenon is the essence of self-organization in cellular automata. An initially random state evolves to a state containing long-range correlations and structure. The bases of the ``triangles'' visible in Fig. 8 are fluctuations in which a sequence of many adjacent cells have the same value. The length of these correlated sequences is reduced by one site per time step, yielding the distinctive triangular structure. Figure 8 suggests that triangles of all sizes are generated. Section 3 confirms this impression through a quantitative analysis and discusses universal features of the structures obtained.
The behavior of the cellular automata shown in Fig. 8 may be characterized in analogy with the behavior of dynamical systems (e.g., Ott, 1981): simple rules exhibit simple limit points or limit cycles, while complex rules exhibit phenomena analogous to strange attractors.
The cellular automata shown in Fig. 8 were all assumed to satisfy periodic boundary conditions. Instead of treating a genuinely infinite line of sites, the first and last sites are identified, as if they lay on a circle of finite radius. Cellular automata can also be rendered finite by imposing null boundary conditions, under which sites beyond each end are modified to maintain value zero, rather than evolving according to the local rules. Figure 9 compares results obtained with these two boundary conditions in a simple case; no important qualitative differences are apparent.
Finite one-dimensional cellular automata are similar to a class of feedback shift registers (e.g., Golomb, 1967; Berlekamp, 1968). (5) A feedback shift register consists of a sequence of sites (``tubes'') carrying values 
. At each time step, the site values evolve by a shift 
and feedback 
where 
give the positions of ``taps'' on the shift register. An elementary cellular automaton of length 
corresponds to a feedback shift register of length with site values 0 and 1 and taps at positions 
, 
and . The Boolean function F defines the cellular automaton rule. [The additive rules 90 and 150 correspond to linear feedback shift registers in which F is addition modulo two (exclusive disjunction).] At each shift register time step, the value of one site is updated according to the cellular automaton rule. After time steps, all sites have been updated, and one cellular automaton time step is complete. All interior sites are treated exactly as in a cellular automaton, but the two end sites evolve differently (their values depend on the two preceding time steps).
. Evolution is shown until a particular configuration appears for the second time, or for at most 30 time steps. Just as in Fig. 3, several classes of behavior are evident. In one class, time evolution generates long-range correlations and fluctuations, yielding distinctive ``triangular'' structures, and exhibiting a simple form of self-organization. All the cellular automata shown are taken to satisfy periodic boundary conditions, so that their sites are effectively arranged on a circle.
