5. Extensions

The results of Secs. 2--4 have for the most part been restricted to elementary cellular automata consisting of a sequence of sites in one dimension with each site taking on two possible values, and evolving at each time step according to the values of its two nearest neighbors. This section gives a brief discussion of the behavior of more complicated cellular automata. Fuller development will be given in future publications.

We consider first cellular automata in which the number of possible values at each site is increased from two, but whose sites are still taken to lie on a line in one dimension. The evolution of each site at each time step is for now assumed to depend on its own value and on the values of its two nearest neighbors. In this case, the total number of possible sets of local rules is . Imposition of the reflection symmetry and quiescence ''legality conditions'' discussed in Sec. 2 introduces constraints, yielding ''legal'' sets of rules. For , this implies legal rules, as considered in Sec. 2. The number of possible legal rules increases rapidly with . For , there are rules, for , , and for , .

As a very simple example of cellular automata with , consider the family of ''modulo-'' rules in which at each time step, the value of a site is taken to be the sum modulo of the values of its two neighbors on the previous time step. This is a generalization of the modulo-two rule (90) discussed on several occasions in Secs. 2--4. Figure 29 shows the evolution of initial states containing a single site with value one according to several modulo- rules. In all cases, the pattern of nonzero sites is seen to tend to a self-similar fractal figure in the large time limit. The pattern in general depends on the value of the nonzero initial site, but in all cases yields an asymptotically self-similar figure. When is prime, independent of the value of the initial nonzero site, a very regular pattern is generated, in which the density of ''triangle structures'' is found to satisfy a one-term recurrence relation yielding a fractal dimension

so that , , and so on. When is a composite number, the pattern generated depends on the value of the initial nonzero site. If the greatest common divisor of and is greater than one (so that and share nontrivial prime factors), then the pattern is identical to that obtained by evolution from an initial site with value one according to a modulo- rule. In general, the density of triangles satisfies a multiple-term recurrence relation. In all cases, the fractal dimension for large behaves as [assuming ]. When , the values of sites become ordinary integers, all with nonzero values by virtue of the nonvanishing values of binomial coefficients, yielding a figure of dimension two.

All modulo- rules obey the additive superposition principle discussed for the modulo two in Secs. 2 and 3. The number of sites with value after evolution for steps from a initial state containing a single site with value one is found [on analogy to Eq. (3.2)] to be , where the function gives the number of occurrences of the digit in the base- decomposition of the integer and generalizes the function introduced in Sec. 3.

[ Figure 29 ] Patterns generated by evolution of one-dimensional cellular automata with states per site according to a modulo- rule, starting from an initial configuration containing a single nonzero site with value one. At each time step, the value of a site is the sum of the values of its two nearest neighbors at the previous time step. Configurations obtained at successive time steps are shown on successive lines. Sites with value zero are indicated as blanks; , , and represent, respectively, values one, two, and three, and in the lower two patterns, represents any nonzero value. In the large time limit, all the patterns tend to a self-similar form, with definite fractal dimensions.

Figure 30 shows typical examples of the behavior of some cellular automata with . Considerable diversity is evident. However, with simple initial states, self-similar patterns are obtained at asymptotically large times, just as in the case of Sec. 3. (Notice that the length and time scales before self-similarity becomes evident are typically longer than those found for : in the limit where each site takes on an arbitrary integer value, self-similarity may not be apparent at any finite time.) Evolution of disordered initial states also again appears to generate nontrivial structure, though several novel phenomena are present. First, alternation of value-one and value-two sites on successive time steps can lead to ''half-speed propagation'' as in rule

Second, rules such as

lead to a set of finite regions containing only sites with values zero and one, separated by ''impermeable membranes'' of value-two sites. The evolution within each region is independent, with the membranes enforcing boundary conditions, and leading to cycles after a finite number of time steps. Third, even for legal rules such as

and

illustrated in Fig. 30, there exist patterns which display a uniform shifting motion. For example, with rule

an isolated shifts to the right by one site every time step, while an isolated shifts to the left; when and meet, they cross without interference. Uniform shifting motion is impossible with legal rules when , since sequences of zero and one sites cannot define suitable directions (evolution of and always yield a pattern spreading in both directions).

An important feature of some cellular automata with more than two states per site is the possibility for the formation of a membrane which ''protects'' sites within it from the effects of noise outside. In this way, there may exist seeds from which very regular patterns may grow, shielded by membranes from external noise typical in a disordered configuration. Examples of such behavior are to be found in Fig. 30. Only when two protective membranes meet is the structure they enclose potentially destroyed. The size of the region affected by a particular seed may grow linearly with time. Even if seeds occur with very low probability, any sufficiently long disordered configuration will contain at least one, and the large time behavior of the cellular automaton will be radically affected by its presence.

[ Figure 30 ] Examples of the evolution of several typical cellular automata with three states per site. Sites with value zero are shown as blanks, while values one and two are indicated by and , respectively. The value of a site at each time step is determined in analogy with Fig. 1 by the digit in the ternary specification of the rule corresponding to the values of the site and its two nearest neighbors at the previous time step. The evolution is shown until a configuration is reached for the second time (signaling a cycle) or for at most thirty time steps. The initial configurations in the lower two rows are typical of disordered configurations in which each site is statistically independent and takes on its three possible values with equal probabilities.

In addition to increasing the number of states per site, the cellular automata discussed above may be generalized by increasing the number of sites whose values affect the evolution of a particular site at each time step. For example, one may take the neighborhood of each site to contain the site itself, its nearest neighbors, and its next-nearest neighbors. With two states per site, the number of possible sets of legal local rules for such cellular automata is (for , this number increases to ). Figure 31 shows patterns generated by these cellular automata for two typical sets of local rules. With simple initial states, self-similar patterns are obtained at large times. With disordered initial states, less structure is apparent than in the three-site neighborhood cellular automata discussed above. The patterns obtained with such cellular automata are again qualitatively similar to those shown in Sec. 2.

The cellular automata discussed so far have all involved a line of sites in one dimension. One may also consider cellular automata in which the sites lie on a regular square or (hyper)cubic lattice in two or more space dimensions. As usual, the value of each site is determined by the values of a neighborhood of sites at the previous time step. In the simplest case, the neighborhood includes a site and its nearest neighbors. However, in dimensions two possible identifications of nearest neighbors can be made. First, sites may be considered neighbors if one of their coordinates differ by one unit, and all others are equal, so that the sites are ''orthogonally'' adjacent. In this case, a ''type-I'' cellular automaton neighborhood containing sites is obtained. Second, sites may be considered neighbors if none of their coordinates differ by more than one unit, so that the sites are ''orthogonally'' or ''diagonally'' adjacent. This case yields a ''type-II'' cellular automaton neighborhood containing sites. When , type-I and -II neighborhoods are identical and each contains three sites. For , the type-I neighborhood contains five sites, while the type-II neighborhood contains nine sites. (14) Cellular automaton rules may be considered legal if they satisfy the quiescence condition and are invariant under the rotation and reflection symmetries of the lattice. For , the number of possible legal type-I rules with states per site is found to be , yielding rules for and for . The number of type-II rules with in two dimensions is found to be (or if reflection symmetries are not imposed).

Figure 32 shows the evolution of an initial configuration containing a single nonzero site according to two-dimensional (type-I) modulo-two rules. In case (a) the value of a site is taken to be the sum modulo two of the values of its four neighbors on the previous time step, in analogy with one-dimensional cellular automaton rule 90. In case (b), the previous value of the site itself is included in the sum (and the complement is taken), in analogy with rule 150. The sequence of patterns obtained at successive time steps may be ''stacked'' to form pyramidal structures in three-dimensional space. These structures become self-similar at large times: in case (a) they exhibit a fractal dimension , and in case (b) a dimension . The patterns found on vertical slices containing the original nonzero site through the pyramids (along one of the two lattice directions) are the same as those generated by the one-dimensional modulo-two rules discussed in Secs. 2 and 3. The patterns obtained at each time step in Fig. 31 are almost always self-similar in the large time limit. For case (a), the number of sites with value one generated after time steps in Fig. 31 is found to be , where gives the number of occurrences of the digit one in the binary decomposition of the integer , as discussed in Sec. 3 (cf. Butler and Ntafos, 1977). The type-I modulo-two rules may be generalized to -dimensional cellular automata. In case (a) the patterns obtained by evolution from a single nonzero initial site have fractal dimension and give nonzero sites at time step . In case (b), the asymptotic fractal dimension is found to be . Once again, simple initial states always yield self-similar structures in the large time limit.

[ Figure 31 ] Evolution of two typical one-dimensional cellular automata with two states per site in which the value of a site at a particular time step is determined by the preceding values of a neighborhood of five sites containing the site, its nearest neighbors, and its next-nearest neighbors. The initial configurations in the lower row are typical of disordered configurations, in which each site has value one with probability .

A particular type-II two-dimensional cellular automaton whose evolution has been studied extensively is the game of ''Life'' (Conway, 1970; Gardner, 1971, 1972; Wainwright, 1971--1973; Wainwright, 1974; Buckingham, 1978; Berlekamp et al., 1982, Chap. 25; R. W. Gosper, private communications). The local rules take a site to ''die'' (attain value zero) unless two or three of its neighbors are ''alive'' (have value one). If two neighbors are alive, the value of the site is left unchanged; if three are alive, the site always takes on the value one. Many configurations exhibiting particular properties have been found. The simplest isolated configurations invariant under time evolution are the ''square'' (or ''block'') consisting of four adjacent live sites, and the ''hexagon'' (or ''beehive'') containing six live sites. ''Oscillator'' configurations which cycle through a sequence of states are also known. The simplest is the ''blinker'' consisting of a line of three live sites, which cycles with a period of two time steps. Oscillators with periods 3, 5, and 7 are also known; other periods may be obtained by composition. So long as they are separated by four or more unfilled sites, many of these structures may exist without interference in the configurations of a cellular automaton, and their effects are localized. There also exist configurations which ''move'' uniformly across the lattice, executing a cycle of a few internal states. The simplest example is the ''glider'' which contains five live sites and undergoes a cycle of length two. The number of filled sites in all the configurations mentioned so far is bounded as a function of time. However, ''glider gun'' configurations have been found which generate infinite streams of gliders, yielding a continually increasing number of live sites. The simplest known glider gun configuration evolves from a configuration containing 26 live cells. Monte Carlo simulation suggests that a disordered state of cells usually evolves to a steady state within about time steps (and typically an order of magnitude quicker); very few of the possible configurations are visited. Complicated structures such as glider guns are very rarely produced. Rough empirical investigation suggests that the density of structures containing live sites generated from a disordered initial state (cf. Buckingham, 1981) decreases like , where is the size of the minimal distinct configuration which evolves to the required structure in one time step. Just as for the one-dimensional cellular automata discussed in Sec. 4, the irreversibility of ''Life'' leads to configurations which cannot be reached by evolution from any other configurations, and can appear only as initial states. However, the simplest known ''unreachable'' configuration contains around 300 sites (Wainwright, 1971--1973; Hardouin-Duparc, 1974; Berlekamp et al., 1982, Chap. 25).

[ Figure 32 ] Evolution of an initial state containing a single nonzero site in a two-dimensional cellular automaton satisfying type-I modulo-two rules. In case (a) the value of each site is taken to be the sum modulo two of the values of its four (orthogonally adjacent) neighbors at the previous time step, while in case (b) the previous value of the site itself is included in the sum, and the complement is taken. Case (a) is the two-dimensional analog of a one-dimensional cellular automaton evolving according to local rule 90, and case (b) of one evolving according to rule 150. The pyramidal structure obtained in each case by stacking the patterns generated at successive time steps is self-similar in the large time limit.

The game of ''Life'' is an example of a special class of ''totalistic'' cellular automata, in which the value of a site depends only on the sum of the values of its neighbors at the previous time step, and not on their individual values. Such cellular automata may arise as models of systems involving additive local quantities, such as chemical concentrations. In one dimension with (and three sites in each neighborhood) all cellular automaton rules are totalistic. In general, the number of totalistic (legal) sets of rules for cellular automata with neighbors for each site is . In one dimension with , of the possible rules are therefore totalistic. Only 243 of the totalistic rules are also peripheral in the sense defined in Sec. 2. With in two dimensions, of the possible rules in a type-I neighborhood are totalistic (and 32 are also peripheral), and of the in a type-II neighborhood.

A potentially important feature of cellular automata is the capability for ''self-reproduction'' through which the evolution of a configuration yields several separated identical copies of the configuration. Figure 33 illustrates a very simple form of self-reproduction with the elementary one-dimensional modulo-two rule (see Waksman, 1969; Amoroso and Cooper, 1971; Fredkin, 1981). With a single nonzero site in the initial state, a configuration containing exactly two nonzero sites is obtained after time steps (15) as indicated by Eq. (3.2). The additive superposition property of the modulo-two rule implies that results for more complicated initial states are obtained by superposition of those for single-site initial states. Thus after time steps, for sufficiently large , the cellular automaton generates two exact copies of any initial sequence of site values. After a further time steps, four copies are obtained. However, after another time steps, the innermost pair of these copies meet again, and annihilate, leaving only two copies when . Purely geometrical ''overcrowding'' thus prevents exponential multiplication of copies by self-reproduction in this case. An exactly analogous phenomenon occurs with the two-dimensional modulo-two rule illustrated in Fig. 32, and its higher-dimensional analogs. In general, the number of sites in a -dimensional cellular automaton configuration grows with time at most as fast as , which is asymptotically slower than the number required for an exponentially increasing number of copies to be generated. Exponential self-reproduction can thus occur only if the copies generated are not precisely identical, but exhibit variability, and for example execute a random walk motion in response to external noise or contain a ''counter'' which causes later generations to ''live'' longer before reproducing.

[ Figure 33 ] Evolution of a simple pattern according to the modulo-two cellular automaton rule (number 90), exhibiting a simple self-reproduction phenomenon. The additive superposition property of the cellular automaton leads to the generation of two exact copies of the initial 1011 pattern at time steps 8, 16, 32,. ''Geometrical overcrowding'' prevents exponential increase in the number of copies produced.

Section 4 mentioned the view of cellular automata as computers. An important class of computers is those with the property of ''computational universality,'' for which changes in input alone allow any ''computable function'' to be evaluated, without any change in internal construction. Universal computers can simulate the operation of any other computer if their input is suitably encoded. Many Turing machines have been shown to be computationally universal. The simplest has seven internal states, and allows four possible ''symbols'' in each square of its tape. One method for demonstrating computational universality of cellular automata shows correspondence with a universal Turing machine. The head of the Turing machine is typically represented by a phononlike structure which propagates along the cellular automaton. It may be shown (Smith, 1971) that an eighteen-state one-dimensional cellular automaton with a three-site neighborhood can simulate the seven-state four-symbol Turing machine in this way, and is therefore computationally universal. Simpler computationally universal cellular automata must be found by other methods. The most straightforward method is to show correspondence with a standard digital computer or electronic circuit by identifying cellular automaton structures which act like ''wires,'' carrying signals without dissipation and crossing without interference, and structures representing NAND gates at intersections between wires. ''Memories'' which maintain the same state for all time are also required. In the Life-game cellular automaton discussed above, streams of gliders generated by glider guns may be used as wires, with bits in the signal represented by the presence or absence of gliders. At the points where ''glider streams'' meet, other structures determine whether the corresponding wires cross or interact through a ''NAND gate.'' The Life-game cellular automaton is thus computationally universal. ''Circuits'' such as binary adders (Buckingham, 1978) may be constructed from Life configurations. It appears that such circuits run at a speed slower than the digital computers to which they correspond only by a constant multiplicative factor. The ''Life game'' is a type-II two-dimensional cellular automaton with two states per site. A computationally universal type-I two-dimensional cellular automaton has been constructed with three states per site (Banks, 1971); only two states are required if the initial configuration is permitted to contain an infinite ''background'' of nonzero sites (Toffoli, 1977a). In one dimension, with a neighborhood of three sites, there are some preliminary indications that a universal cellular automaton may be constructed with five states per site. The details and implications of this cellular automaton will be described in a future publication.

previous  l  next