Computation Theory

While dynamical systems theory concepts suffice to define class 1, 2 and 3 cellular automata, computation theory is apparently required for class 4 cellular automata. Examples of the evolution of a typical class 4 cellular automaton are shown in Fig. 5. Varied and complicated behaviour, involving many different time scales is evident. Persistent structures are often generated; the smallest few are illustrated in Fig. 6, and are seen to allow both storage and transmission of information. It seems that the structures supported by this and other class 4 cellular automata rule may be combined to implement arbitrary information processing operations. Class 4 cellular automata would then be capable of universal computation: with particular initial states, their evolution could implement any finite algorithm. (Universal computation has been proved for a , rule [22], and for two-dimensional cellular automata such as the `Game of Life' [22,23].) A few per cent of cellular automaton rules with or are found to exhibit class 4 behaviour: all these would then, in fact, be capable of arbitrarily complicated behaviour. This capability precludes a smooth infinite size limit for entropy or other quantities: as the size of cellular automaton considered increases, more and more complicated phenomena may appear.

Cellular automaton evolution may be viewed as a computation. Effective prediction of the outcome of cellular automaton evolution requires a short-cut that allows a more efficient computation than the evolution itself. For class 1 and 2 cellular automata, such short cuts are clearly possible: simple computations suffice to predict their complete future. The computational capabilities of class 3 and 4 cellular automata may, however, be sufficiently great that, in general, they allow no short-cuts. The only effective way to determine their evolution from a given initial state would then be by explicit observation or simulation: no finite formulae for their general behaviour could be given. (If class 4 cellular automata are indeed capable of universal computation, then the variety of their possible behaviour would preclude general prediction, and make explicit observation or simulation necessary.) Their infinite time limiting behaviour could then not, in general, be determined by any finite computational process, and many of their limiting properties would be formally undecidable. Thus, for example, the `halting problem' of determining whether a class 4 cellular automaton with a given finite initial configuration ever evolves to the null configuration would be undecidable. An explicit simulation could determine only whether halting occurred before some fixed time, and not whether it occurred after an arbitrarily long time.

For class 4 cellular automata, the outcome of evolution from almost all initial configurations can probably be determined only by explicit simulation, while for class 3 cellular automata this is the case for only a small fraction of initial states. Nevertheless, this possibility suggests that the occurrence of particular site value sequences in the infinite time limit is in general undecidable. The large time limit of the entropy for class 3 and 4 cellular automata would then, in general, be non-computable: bounds on it could be given, but there could be no finite procedure to compute it to arbitrary precision. (This would be the case if the limit sets for class 3 and 4 cellular automata formed at least context-sensitive languages.)

While the occurrence of a particular length site value sequence in the infinite time limit may be undecidable, its occurrence after any finite time can, in principle, be determined by considering all length initial sequences that could evolve to it. For increasing or this procedure would nevertheless, involve exponentially-growing computational resources, so that it would rapidly become computationally intractable. It seems likely that the identification of possible sequences generated by class 3 and 4 cellular automata is, in general, an NP-complete problem (see ref. [15]). It can, therefore, presumably not be solved in any time polynomial in or , and essentially requires explicit simulation of all possibilities.

Undecidability and intractability are common in problems of mathematics and computation. They may well afflict all but the simplest cellular automata. One may speculate that they are widespread in natural systems, perhaps occurring almost whenever nonlinearity is present. No simple formulae for the behaviour of many natural systems could then be given; the consequences of their evolution could be found effectively only by direct simulation or observation.

I thank O. Martin, J. Milnor, N. Packard and many others for discussions. The computer mathematics system SMP [24] was used during this work. The work was supported in part by the US Office of Naval Research (contract No. N00014-80-C-0657).

previous  l  next