Problem 18

How common is computational irreducibility in cellular automata?

One way to find out the behaviour of a cellular automaton is to simulate each step in its evolution explicitly. The question is how often there are better ways.

Cellular automaton evolution can be considered as a computation. A procedure can short cut this evolution only if it involves a more sophisticated computation. But there are cellular automata capable of universal computation that can perform arbitrarily sophisticated computations. So at least in these cases no short cut procedure can in general be found. The cellular automaton evolution corresponds to an irreducible computation, whose outcome can be found effectively only by carrying it out explicitly.

A number of complications arise in giving a precise definition of such computational irreducibility. In general one should compare the number of steps in the evolution of a system such as a cellular automaton with the number of steps required to reproduce the evolution using another computational system. However, by making the computational system more complicated, it is always possible to reduce the number of steps required by an arbitrary constant factor, or even an arbitrary function. For example, if a computer can apply the square of a cellular automaton mapping at each step, then it can always simulate steps of cellular automaton evolution in steps.

Nevertheless, no amount of additional complication in the computer can allow it to find in a finite time the outcome of an infinite number of steps in the evolution of a cellular automata that is for example capable of universal computation. As a consequence, there are undecidable propositions about the ultimate behaviour of the cellular automaton. The occurrence of such undecidable propositions may be viewed as a consequence of computational irreducibility. But to give a complete definition of computational irreducibility for finite time processes, one must in some way exclude arbitrary complication in the computer used for predictions.

One approach is to consider finite cellular automata and to use methods from computational complexity theory. A cellular automaton with sites can evolve for a time up to before retracing its steps. The computation corresponding to this evolution is performed in a bounded space, and is therefore in the class PSPACE (e.g., [8]), but it can take a time exponential in . However if the computation were reducible, then it could be possible to find the outcome of the evolution in a time polynomial in , or in other words to reduce the problem to one in the class . It is believed that PSPACE , so that there exist problems that can be solved in polynomial space that cannot be solved in polynomial time. Determining the outcome of the evolution of some cellular automata may be a problem of this kind (cf. [52]).

Conventional computational complexity theory concerns computations in finite systems. It may well be that the definition of computational irreducibility for cellular automata can be sharpened in the infinite size limit.

The evolution of class 1 and 2 cellular automata yielding periodic configurations is computationally reducible. But one suspects that the evolution of most class 3 and 4 cellular automata is computationally irreducible. In fact, it may well be in general that most systems that show apparently complex or chaotic behaviour are computationally irreducible.

Even if the detailed behaviour of a system can effectively be found only by direct simulation, it could be that many of its overall properties can be found by more efficient procedures. It is this possibility that makes investigations of cellular automata worthwhile even when computational irreducibility is present. But what should be done is to find a characterization of those properties whose behaviour can be found by efficient methods, and those for which computational irreducibility makes explicit simulation the only possible approach, and precludes a simple description.

previous  l  next