8. Computation Theoretical Properties

The discussion of the previous section can be considered as giving a characterization of the computational complexity of iterations of the cellular automaton mapping (3.1) in a particular simple model of computation. The results obtained suggest that at least in this model, there is no shortcut method for finding the outcome of the evolution: the computations required are no less than for an explicit simulation of each time step. As discussed above, one suspects in fact that the evolution is in general computationally irreducible, so that no possible computation could find its outcome more efficiently than by direct simulation.

This would be the case if the cellular automaton of Eq. (3.1) could act as an efficient universal computer (e.g., [33]), so that with an appropriate initial state, its evolution could mimic any possible computation. In particular, it could be that the problem of finding the value of a particular site after steps (given say a simply-specified initial state, as in Fig. 6.1) must take a time polynomial in on any computer. (Direct simulation takes time on a serial-processing computer, and time with parallel processors.) For a linear cellular automaton such as that of Eq. (2.4), this problem can be solved in a time polynomial in ; but for the cellular automaton of Eq. (3.1) it quite probably cannot [18].

In addition to studying cellular automaton evolution from given initial configurations, one may consider the problem of deducing configurations of the cellular automaton from partial information such as temporal sequences. In particular, one may study the computational complexity of finding the seed for a cellular automaton in a finite region from the temporal sequences it generates.

There are possible seeds for a size cellular automaton, and one can always find which ones produce a particular sequence by trying each of them in turn. Such a procedure would however rapidly become impractical. The results in Section 7 suggest a slightly more efficient method. If it were possible to find two adjacent temporal sequences, then the seed could be found easily using Eq. (3.3). Given only one temporal sequence, however, some elements of the seed are initially undetermined. Nevertheless, in a finite size system, say with periodic boundary conditions, one can derive many distinct equations for a single site value. The site value can then be deduced by solving the resulting system of simultaneous Boolean equations. The equations will however typically involve many variables. As discussed in Section 7, the number of variables seems to be Poisson-distributed with a mean around .

The general problem of solving a Boolean equation in variables is NP-complete (e.g., [5]), and so presumably cannot be solved in a time polynomial in . In addition, it seems likely that the average time to solve an arbitrary Boolean equation is correspondingly long. To relate the problem of deducing the seed discussed above to this would however require a demonstration that the Boolean equations generated were in a sense uniformly distributed over all possibilities. Out of all -variable equations, the problem here typically involves , but these seem to have no special simplifying features. At least with the method discussed above, it is thus conceivable that the problem of deducing the seed is equivalent to the general problem of solving Boolean equations, which is NP-complete.

previous  l  next