8. Class 4 Cellular Automata

Figure 12 shows the evolution of the class 4 cellular automaton with , and code number 20, from several disordered initial configurations. In most cases, all sites are seen to ``die'' (attain value zero) after a finite time. However, in a few cases, stable or periodic structures which persist for an infinite time are formed. In addition, in some cases, propagating structures are formed. Figure 13 shows the persistent structures generated by this cellular automaton from all initial configurations whose nonzero sites lie in a region of length 20 (reflected versions of the last three structures are also found). Table 3 gives some characteristics of these structures. An important feature, shared by other class 4 cellular automata, is the presence of propagating structures. By arranging for suitable reflections of these propagating structures, final states with any cycle lengths may be obtained.

The behaviour of the cellular automata illustrated in fig. 13, and the structures shown in fig. 14 are strongly reminiscent of the two-dimensional (essentially totalistic) cellular automaton known as the ``Game of Life'' (5) (for references see [1]). The Game of Life has been shown to have the important property of computational universality. Cellular automata may be viewed as computers, in which data represented by initial configurations is processed by time evolution. Computational universality (e.g. [15], [16], [17] and [18]) implies that suitable initial configurations can specify arbitrary algorithmic procedures. The system can thus serve as a general purpose computer, capable of evaluating any (computable) function. Given a suitable encoding, the system may therefore in principle simulate any other system, and in this sense may be considered capable of arbitrarily complicated behaviour.

The proof of computational universality for the Game of Life [22] uses the existence of cellular automaton structures which emulate components (such as ``wires'' and ``NAND gates'') of a standard digital computer. The structures shown in fig. 14 represent a significant fraction of those necessary. A major missing element is a configuration (dubbed the ``glider gun'' in the Game of Life) which acts like a clock, and generates an infinite sequence of propagating structures. Such a configuration would involve a finite number of initial nonzero sites, but would lead to unbounded growth, and an asymptotically infinite number of nonzero sites. There are however indications that the required initial configuration is quite large, and is very difficult to find.

[ Figure 12 ] Examples of the evolution of a class 4 cellular automaton (totalistic code 20 , rule) from several disordered initial states. Persistent structures are seen to be generated in a few cases. The evolution is truncated after 120 time steps.

These analogies lead to the speculation that class 4 cellular automata are characterized by the capability for universal computation. , cellular automata are too simple to support universal computation; the existence of class 4 cellular automata with , (cf. figs. 13 and 14) and , suggests that with suitable time evolution rules even such apparently simple systems may be capable of universal computation.

[ Table 3 ] Persistent structures arising from initial configurations with length less than 20 sites in the class 4 totalistic cellular automaton with , and code number 20, illustrated in figs. 12, 13 and 14. gives the fraction of initial configurations with nonzero sites in a region less than sites in length which generate a particular structure. When an initial configuration yields multiple structures, each is included in this fraction.

There are important limitations on predictions which may be made for the behaviour of systems capable of universal computation. The behaviour of such systems may in general be determined in detail essentially only by explicit simulation of their time evolution. It may in general be predicted using other systems only by procedures ultimately equivalent to explicit simulation. No finite algorithm or procedure may be devised capable of predicting detailed behaviour in a computationally universal system. Hence, for example, no general finite algorithm can predict whether a particular initial configuration in a computationally universal cellular automaton will evolve to the null configuration after a finite time, or will generate persistent structures, so that sites with nonzero values will exist at arbitrarily large times. (This is analogous to the insolubility of the halting problem for universal Turing machines (e.g. [15], [16], [17] and [18]).) Thus if the cellular automaton of figs. 12 and 13 is indeed computationally universal, no finite algorithm could predict whether a particular initial state would ultimately ``die'', or whether it would ultimately give rise to one of the persistent structures of fig. 13. The result could not be determined by explicit simulation, since an arbitrarily large time might elapse before one of the required states was reached. Another universal computer could also in general determine the result effectively only by simulation, with the same obstruction.

If class 4 cellular automata are indeed capable of universal computation, then their evolution involves an element of unpredictability presumably not present in other classes of cellular automata. Not only does the value of a particular site after many time steps potentially depend on the values of an increasing number of initial site values; in addition, the value cannot in general be determined by any ``short-cut'' procedure much simpler than explicit simulation of the evolution. The behaviour of a class 4 cellular automaton is thus essentially unpredictable, even given complete initial information: the behaviour of the system may essentially be found only by explicitly running it.

Only infinite cellular automata may be capable of universal computation; finite cellular automata involve only a finite number of internal states, and may therefore evaluate only a subset of all computable functions (the ``space-bounded'' ones).

The computational universality of a system implies that certain classes of general predictions for its behaviour cannot be made with finite algorithms. Specific predictions may nevertheless often be made, just as specific cases of generally noncomputable function may often be evaluated. Hence, for example, the behaviour of all configurations with nonzero sites in a region of length 20 or less evolving according to the cellular automaton rules illustrated in figs. 12 and has been completely determined. Figure 14 shows the fraction of initial configurations which evolve to the null state within time steps, as a function of , for various sizes of the region of nonzero sites. For large and large , it appears that the fraction of configurations which generate no persistent structures (essentially the ``halting probability'') is approximately 0.93. It is noteworthy that the curves in fig. 14 as a function of appear to approach a fixed form at large . One may speculate that some aspects of the form of such curves may be universal to all systems capable of universal computation.

[ Figure 13 ] Persistent structures found in the evolution of the class 4 cellular automaton illustrated in fig. 12 from initial states with nonzero sites in a region of 20 or less sites. Reflected versions of the last three structures are also found. Some properties of the structures are given in Table 3. These structures are almost sufficient to provide components necessary to demonstrate a universal computation capability for this cellular automaton.

[ Figure 14 ] Fraction of configurations in the class 4 cellular automaton of figs. 12 and which evolves to the null configuration after time steps, from initial states with nonzero sites in a region of length less than (translates of configurations are not included). The asymptotic ``halting probability'' is around 0.93; 7% of initial configurations generate the persistent structures of fig. 13 and never evolve to the null configuration.

The sets of persistent structures generated by class 4 cellular automata typically exhibit no simple patterns, and do not appear to be specified, for example, by regular grammars. Specification of persistent structures by a finite procedure is necessarily impossible if class 4 cellular automata are indeed capable of universal computation. Strong support of the conjecture that class 4 cellular automata are capable of universal computation would be provided by a demonstration of the equivalence of systematic enumeration of all persistent structures in particular class 4 cellular automata to the systematic enumeration of solutions to generally insoluble Diophantine equations or word problems.

Although one may determine by explicit construction that specific cellular automata are capable of universal computation, it is impossible to determine in general whether a particular cellular automaton is capable of universal computation. This is a consequence of the fact that the structures necessary to implement universal computation may be arbitrarily complicated. Thus, for example, the smallest propagating structure might involve an arbitrarily long sequence of site values.

For class 1, 2 and 3 cellular automata, fluctuations in statistical quantities are typically found to become progressively smaller as larger numbers of sites are considered. Such systems therefore exhibit definite properties in the ``infinite volume'' limit. For class 4 cellular automata, it seems likely that fluctuations do not decrease as larger number of sites are considered, and no simple smooth infinite volume limit exists. Important qualitative effects can arise from special sequences appearing with arbitrarily low probabilities in the initial state. Consider for example the class 4 cellular automaton illustrated in figs. 12 and 13. The evolution of the finite sequences in this cellular automaton shown in fig. 12 (and many thousands of other finite sequences tested) suggests that the average density of nonzero sites in configurations of this cellular automaton should tend to a constant at large times. However, in a sufficiently long finite initial sequence, there should exist a subsequence from which a ``glider gun'' structure evolves. This structure would generate an increasing number of nonzero sites at large times, and its presence would completely change the average large time density. As a more extreme example, it seems likely that a sufficiently long (but finite) initial sequence should evolve to behave as a self-reproducing ``organism'', capable of eventually taking over its environment, and leading to completely different large time behaviour. Very special, and highly improbable, initial sequences may thus presumably result in large changes in large time properties for class 4 cellular automata. These sequences must appear in a truly infinite (typical) initial configuration. Although their density is perhaps arbitrarily low, the sequences may evolve to structures which come to dominate the statistical properties of the system. The possibility of such phenomena suggest that no smooth infinite volume exists for class 4 cellular automata.

Some statistical results may be obtained from large finite class 4 cellular automata, although the results are expected to be irrelevant in the truly infinite volume limit. The evolution of most class 4 cellular automata appears to be highly irreversible. (6) This irreversibility is reflected in the small set of persistent structures usually generated as end-products of the evolution. Changes in small regions of the initial state may affect many sites at large times. There are however very large fluctuations in the propagation speed, and no meaningful averages may be obtained. It should be noted that groups of class 4 cellular automata with different rules often yield qualitatively similar behaviour, and similar sets of persistent structures, suggesting further classification.

The frequency with which a particular structure is generated after an infinite time by the evolution of a universal computer from random (disordered) input gives the ``algorithmic probability'' [24] for that structure. This algorithmic probability has been shown to be invariant (up to constant multiplicative factors) for a wide class of universal computers. In general, one may define an ``evolutionary probability'' which gives the probability for a structure to evolve after time steps from a random initial state. Complex structures formed by cellular automata will typically have evolutionary probabilities which are initially small, but later grow. As a simple example, the probability for the sequence which yields a period 9 propagating structure in the cellular automaton of figs. 12 and 13 begins small, but later increases to a sufficiently large value that such structures are almost always generated from disordered states of 2000 or more sites. In a much more complicated example, one may imagine that the probability for a self-reproducing structure begins small, but later increases to a substantial value. Structures whose evolutionary probability becomes significant only after a time may be considered to have ``logical depth'' [25] .

previous  l  next