Problem 16

How common are computational universality and undecidability in cellular automata?

If a system is capable of universal computation, then with appropriate initial conditions, its evolution can carry out any finite computational process. A computationally universal system can thus mimic the behaviour of any other system, and so can in a sense exhibit the most complicated possible behaviour.

Several specific cellular automata are known to be capable of universal computation. The two-dimensional nearest-neighbour cellular automaton with two possible values at each site known as the ``Game of Life'' has been proved computation universal [47]. The proof was carried out by showing that the cellular automaton could support structures that correspond to all the components of an idealized digital electronic computer, and that these components could be connected so to implement any algorithm. Some one-dimensional nearest-neighbour cellular automata with have been shown to be computationally equivalent to the simplest known universal Turing machines, and are thus capable of universal computation [48].

One speculates that cellular automata identified on statistical grounds as class 4 are in fact generically capable of universal computation. This would imply that there exist one-dimensional computationally universal cellular automata in cases as simple as , or , . But it remains to prove the computational universality of any particular such rule. Several methods could be used for such a proof. One is to identify a set of persistent structures in the cellular automaton that could act as the components of a digital computer, or like combinations of symbols and internal states for a Turing machine. Structures that remain fixed, propagate, and interact in various ways have been found. A structure that can act as a ``clock'', producing an infinite sequence of ``signals'', has not yet been found in such cellular automata. Another method of proving universality would be a direct demonstration that this cellular automaton rule could simulate any other cellular automaton rule with an appropriate encoding of initial states. Blocking transformations may provide the necessary encodings: so one must find out whether a particular cellular automaton rule is connected to all others in the simulation networks constructed from blocking transformations.

If class 4 cellular automata are indeed capable of universal computation, then the capability for universal computation is quite common among one-dimensional cellular automata. Class 4 behaviour is however much rarer in two dimensional cellular automata---the ``Game of Life'' is almost the only known example (cf. [12]).

There may well be cellular automata whose behaviour is usually computationally simple, but which with very special initial states can perform arbitrary computations. It is certainly possible to construct cellular automata in which universal computation occurs only with initial states in which say every other site has value zero (cf. [49]), a condition that occurs in disordered states with probability zero. Such phenomena may be common in class 3 cellular automata.

Any predictions about the behaviour of a cellular automaton must be made by performing some computation. But if the cellular automaton is capable of universal computation, then this computation must in general reduce to a direct simulation of the cellular automaton evolution. So questions about the infinite time limiting behaviour of cellular automata may require infinite computations, and therefore be formally undecidable.

For example, one may consider the question of whether the patterns generated from particular finite initial seeds ever die out in the evolution of the cellular automaton. One may simulate the evolution explicitly to find out whether a pattern dies out after say a thousand time steps; but to determine its ultimate fate in general requires a computation of unbounded length. The question is therefore formally undecidable.

The set of finite configurations that evolve to the null configuration after a fixed finite time can be specified by a regular formal language (cf. [50]). But there is no such finite specification for the set of finite configurations that evolve after any time to the null configuration. Even the fraction of configurations in this set is in general a non-computable number.

A similar problem is to determine whether a particular finite sequence of site values occurs in any configurations in the limit set for a cellular automaton. Again this problem is in general undecidable [40]. An explicit finite calculation can show that a sequence is forbidden after say three time steps. But a particular sequence may only be forbidden after some arbitrarily large number of time steps. In a one-dimensional cellular automaton, the length of the shortest sequence newly excluded at a given time step in the evolution is bounded by . In most actual examples seems to increase monotonically with time, so that the exclusion of a particular finite sequence must occur before some predictable finite time. But in some cases is not monotonic, and the occurrence of particular sequences may be undecidable.

The capability for universal computation can be used to establish the undecidability of questions about the behaviour of a system. But undecidability can occur even in systems not capable of full universal computation. For example, one may arrange to disable all computations that give results of a certain form. In this way, the system fails to be able to perform arbitrary computations. Nevertheless, there may be undecidable questions about the class of computations that it still can perform. These may well occur in cellular automata. Proofs of undecidability usually use a diagonal argument based essentially on universal computation. To establish undecidability in a system not itself capable of universal computation, one must usually find another system that is capable of universal computation, and show that a reduction of its capabilities does not affect undecidability.

Rice's theorem states that almost all questions about an arbitrary recursively-enumerable set are undecidable (e.g., [8]). However, it may be that natural or simple questions, which can be stated in say a few logical symbols, are usually decidable. So for example the halting of all simple initial seeds in a particular cellular automaton might be easy to determine, and it might only be very large and specially-chosen initial seeds whose halting was difficult to determine. There are certainly examples in which the halting problem appears to be difficult to answer even for simple seeds. One must establish in general not only whether there are any undecidable propositions about the behaviour of a particular cellular automaton, but whether simple propositions about it are in fact undecidable.

previous  l  next