7. Functional Properties

Cellular automaton rules such as (3.1) can be considered as functions which map three Boolean values to one. Iterations of these rules for say steps correspond to functions of Boolean values. The complexity of these functions reflects the intrinsic complexity of the cellular automaton evolution.

The complexity of a Boolean function can be characterized by the number of logic gates that would be needed to evaluate it with a particular kind of circuit, or the number of terms that it would have in a particular symbolic representation. Explicit evolution according to the cellular automaton rule (3.1) corresponds to a circuit with components and depth . But for purposes of comparison, it is convenient to consider fixed depth representations. One such representation is disjunctive normal form (DNF), in which the function is written as a disjunction of conjunctions. A two-level circuit can be constructed in direct correspondence with this form (as programmable logic arrays often are).

For the function of Eq. (3.1), the DNF is

where stands for , concatenation for , and bar for . Notice that by using in addition an operation, Eq. (3.1) itself gives a shorter form for this function.

The general problem of finding the absolute shortest representation for an arbitrary Boolean function, even in DNF, is NP-complete (e.g., [5]), and so presumably requires an exponential time computation. But a definite approximation can be found in terms of ''prime implicants'' (e.g., [28]). A Boolean function of variables can be considered as a colouring of the Boolean -cube. Prime implicants give the hyperplanes (with different dimensions) in the -cube which must be superimposed to obtain the region with value 1. Each prime implicant can thus be used as a term in a DNF for the function. The number of prime implicants required gives a measure of the total number of ''holes'' in the colouring of the -cube, and thus of the complexity of the function.

[ Table 7.1 ] Number of terms in disjunctive normal form Boolean expressions corresponding to iterations of the mappings (3.1) (CA30) and (2.4) (CA60). P.I. gives the number of prime implicants; min. the number of terms obtained by [29]. (The two numbers are the equal in the case of Eq. (2.4).)

The minimal DNF obtained with prime implicants for the function corresponding to two iterations of the cellular automaton mapping (3.1) is

Table 7.1 gives the number of prime implicants for successive iterations of the mapping (3.1). These results are plotted in Fig. 7.1. For arbitrary Boolean functions of variables, the number of prime implicants could increase like . In practice, however, a least squares fit to the data of Table 7.1 suggests growth like .

Various efficient methods are known to find DNF that are somewhat simpler than those obtained using prime implicants. With one such method [28, 29], the DNF of Eq. (7.2) can be reduced to

The sizes of the minimal DNF obtained by this method for iterations of Eq. (3.1) are shown in Table 7.1 and Fig. 7.1. They are seen to grow more slowly than those obtained with prime implicants; the data given are however again fit by exponential growth like .

Table 7.1 and Fig. 7.1 also give the size of the minimal DNF for iterations of the linear cellular automaton mapping (2.4). This number remains much smaller, apparently increasing like , where gives the number of ones in the binary representation for the integer (cf. [30]).

The rapid increase in the size of the minimal DNF found for iterations of Eq. (3.1) indicates the increasing computational complexity of determining the result of evolution according to (3.1), and supports the conjecture of its computational irreducibility. (Note however that even the parity function cannot be computed by any DNF, or in general fixed-depth, circuit of polynomial size [31].)

[ Figure 7.1 ] Number of terms in disjunctive normal form Boolean expressions for step iterations of the mappings (3.1) and (2.4). The upper curve gives the number of prime implicants for iterations of Eq. (3.1). The next curve gives the minimal number of terms obtained in this case using [29]. The lowest curve gives the minimal number of terms for the linear cellular automaton mapping (2.4).

Equation (7.3) gives the function which determines the value of a single site after two iterations of the cellular automaton rule (3.1). One can also construct a function which gives the length sequence of values of a particular site attained through time by evolution from a given length initial sequence. The minimal DNF representation for this function is found (using [29]) to grow in size approximately as .

The results of Table 7.1 and Fig. 7.1 concern the difficulty of finding the outcome of cellular automaton evolution according to Eq. (3.1) from a given initial state. One may also consider the problem of deducing the initial state from time sequences of site values produced in the evolution. Given say steps in the time sequence of values for two adjacent sites, the initial configuration up to sites to the left can be deduced directly by iteration of Eq. (3.3). The combinatorial results of Section 4 indicate in fact that only about 1.2 such temporal sequences should on average be required. And in principle from a single sufficiently long temporal sequence, it should be possible to deduce a complete initial configuration for a finite cellular automaton. In practice, however, the necessary computation seems to become increasingly intractable as the size of the system increases.

Given a particular temporal sequence, say at position 0, Eq. (3.3) uniquely determines the values of all sites in a triangle to the left as a function of values in the temporal sequence at position 1. The number of values in the position 1 temporal sequence on which a given site depends varies with the form of the position 0 sequence [32]. For example, if the position 0 sequence consists solely of ones, then the whole triangle of sites is completely determined, entirely independent of the position 1 sequence. Table 7.2 gives some results from considering the dependence of the site value at position (the apex of the triangle) on the position 1 sequence, for all possible position 0 sequences. The number of values in the position 1 sequence on which depends seems to be roughly Poisson distributed, with a mean that grows like , as shown in Fig. 7.2. This is consistent with the combinatorial result (4.6).

[ Table 7.2 ] Properties of Boolean expressions for leftmost initial site values deduced from length time sequences, obtained by evolution according to Eq. (3.1). The average number of variables appearing in the Boolean expressions is given, together with the number of prime implicants in the disjunctive normal form for the expression. The maximum number of variables which can appear is always . (Results for were obtained by Carl Feynman using a Symbolics 3600 LISP machine. The entries left blank were not found.)

[ Figure 7.2 ] Average number of additional site values necessary to ''back-track'' and determine uniquely the initial site value given the sequence of values for subsequent time steps.

Table 7.2 also gives some properties of the prime implicant forms for . It is clear that the complexity of the function that determines from temporal sequences grows with , probably at an increasingly rapid rate. Again this suggests that the problem of deducing the initial sequence for evolution according to Eq. (3.1), while combinatorially possible, is computational complex.

By comparison, the corresponding problem for evolution according to the linear rule (2.4) is quite straightforward. For each possible position 0 sequence, there are only two possible forms for the dependence of on the position 1 sequence, and each of them involves exactly prime implicants. This simplicity can be viewed as a consequence of the algebraic structure associated with this system.

previous  l  next