4. Global Properties

Section 3 discussed the typical behavior of cellular automata evolving from particular initial states. This section considers the global properties of cellular automata, determined by evolution from all possible initial states. Studies of the global properties of one-dimensional cellular automata have been made using methods both from dynamical systems theory and from computation theory. Here these studies are generalized to the case of two-dimensional cellular automata. For those based on dynamical systems theory the generalization is quite straightforward; but in the computation theory approach substantial additional complications occur. Whereas the sets of configurations generated after any finite number of steps in the evolution of one-dimensional cellular automata always correspond to regular formal languages, the corresponding sets in two-dimensional cellular automata may be nonrecursive.

Most cellular automaton rules are irreversible, so that several different initial states may evolve to the same final state. As a consequence, even starting from all possible initial states, only a subset of possible states may be generated with time. The properties of this set then determine the overall behavior of the cellular automaton, and the self-organization that occurs in it.

Entropy and dimension provide quantitative characterizations of the ``sizes'' of sets generated by cellular automaton evolution (e.g., Ref. 7). The spatial set entropy for a set of two-dimensional cellular automaton configurations is defined by considering a patch of sites. If the set contains all possible configurations, then all possible different arrangements of sites values must occur in the patch. In general different arrangements will occur. Then the set entropy (or dimension) is defined as

If the cellular automaton mapping is surjective, so that all possible configurations occur, then this entropy is equal to one. In general it decreases with time in the evolution of the cellular automaton.

Spatial set entropy characterizes the set of configurations that can possibly be generated in the evolution of a cellular automaton, regardless of their probabilities of occurrence. One may also define a spatial measure entropy in terms of the probabilities for possible patches as

The limiting value of at large times is typically nonzero for all but class-1 cellular automaton rules. Notice that in cases where domains with positive ``surface tension'' are formed, tends only very slowly to zero with time.

To find the spatial set entropy after, say, one time step in the evolution of a cellular automaton one must identify what configurations can be generated. In a one-dimensional cellular automaton, one can specify the set of configurations that can be generated in terms of rules that determine which sequences of site values can appear. These rules correspond to a regular formal grammar, and give the state transition graph for a finite state machine. The set of configurations that can be generated in a two-dimensional cellular automaton is more difficult to specify. In many circumstances in fact the occurrence of a particular patch of site values requires a global consistency that cannot be verified in general by any finite computation. As a consequence, many propositions concerning sets of configurations generated after even a finite number of steps in the evolution of two-(and higher-)dimensional cellular automata can be formally undecidable.

In a one-dimensional cellular automaton with a range- rule, a particular sequence of site values can be generated (reached) after one time step only if there exists some length sequence of initial site values that evolves to it. The locality of the cellular automaton rule ensures that in determining whether a length sequence obtained by appending one new site can also be generated, it suffices to test only those length predecessor configurations that differ in their last site values. In determining whether sequences of progressively greater lengths can be generated it suffices at each stage to record with which length overlaps in the predecessor configuration a particular new site value can be appended. Since there are only possible sequences of site values in the overlaps, only a finite amount of information must be recorded, and a finite procedure can be given for determining whether any given sequence can be generated (cf. Ref. 12). Hence in particular there is a finite procedure to determine whether any given cellular automaton rule is surjective, so that all possible configurations can be reached in its evolution.

In two-dimensional cellular automata there is no such simple iterative procedure for determining whether progressively larger patches of site values can be generated. An patch of site values is generated after one step in the evolution of a two-dimensional cellular automaton with a range- rule if there exists some patch of initial site values that evolves to it. Progressively larger patches can be generated if appropriate progressively larger predecessor patches exist. The number of sites in the overlap between such progressively larger predecessor patches is not fixed, as in one-dimensional cellular automata, but instead grows essentially like the perimeter of the patch, . With this procedure, there is thus no upper bound on the amount of information that must be recorded to determine whether progressively larger patches can be generated. To find whether a patch of any particular size can be generated, it suffices to test all candidate predecessor patches. (As mentioned below, this is in fact an NP-complete problem, and therefore presumably cannot be solved in general in a time polynomial in the patch size.) However, questions concerning complete configurations can be answered only by considering arbitrarily large patches, and may require arbitrarily complex computations. As a consequence, there are global questions about configurations generated by two-dimensional cellular automata after a finite number of time steps that can posed, but cannot in general be answered by any finite computational process, and are therefore formally undecidable.

Some examples of such undecidable questions about two-dimensional cellular automata are: (i) whether a particular complete (but finitely specified) configuration can be generated after one time step from any initial configuration; (ii) whether a particular cellular automaton rule is surjective, so that all possible configurations can be generated; (iii) whether the set of complete configurations generated after say one time step has a nonempty intersection with some recursive formal language such as a regular language, whose words can be recognized by a finite computation; (iv) whether there exist configurations that have a particular period in time (and are thus invariant under some number of iterations of the cellular automaton rule).

It seems that global questions about the finite time behavior of one-dimensional cellular automata are always decidable. Questions about their ultimate infinite time behavior may nevertheless be undecidable. To show this, one considers one-dimensional cellular automata whose evolution emulates that of a universal Turing machine. The successive arrangements of symbols on the Turing machine tape correspond to successive configurations of site values generated in the evolution of the cellular automaton. Undecidable questions such as halting for the Turing machines are then shown to be undecidable for the corresponding one-dimensional cellular automaton.

In two-dimensional cellular automata, questions about global properties on infinite spatial scales can be undecidable even at finite times. This is proved by considering the line-by-line construction of configurations. The rules used to obtain each successive line from the last can correspond to the rules for a universal Turing machine. The construction of the configuration can then be continued to infinity and completed only if this Turing machine does not halt with the input given, which is in general undecidable. Sets of configurations generated at finite times in the evolution of two-dimensional cellular automata can thus be nonrecursive.

Many global questions about two-dimensional cellular automata are closely analogous to geometrical questions associated with tilings of the plane. Consider for example the problem of finding configurations that remain invariant under a particular cellular automaton rule. All the neighborhoods in such configurations must be such that the values of their center sites are left unchanged by the cellular automaton rule. Each such neighborhood may be considered as a ``tile.'' Complete invariant configurations are constructed from an array of tiles, with each adjacent pair of tiles subject to a consistency condition that the overlapping sites in the neighborhoods to which they correspond should agree. In a one-dimensional cellular automaton, the set of possible arrangements of tiles or configurations that satisfy the conditions can be enumerated immediately, and form a finite complement regular language (subshift of finite type). In a two-dimensional cellular automaton, the problem of finding invariant configurations is equivalent to tiling the plane with a set of ``dominoes'' corresponding to the possible allowed neighborhoods, and subject to constraints that can be cast in the form of requiring adjacent pairs of edges to have complementary colors. The problem of determining whether a particular set of dominoes can in fact be used to tile the plane is however known to be undecidable (cf. Ref. 34). The problem of finding whether there exist invariant configurations under a particular two-dimensional cellular automaton rule is likewise undecidable.

If any infinite sequence can be constructed from some set of dominoes in one dimension, then it is clear that a spatially periodic sequence can be found. Hence if there are to be any configurations with a particular temporal period in a one-dimensional cellular automaton, then there must be spatially periodic configurations with this temporal period. (The maximum necessary spatial period for configurations with temporal period is : the existence of such spatially periodic configurations can be viewed as a consequence of the pumping lemma (e.g., Ref. 11) for regular languages.) In two dimensions, however, there are sets of dominoes for which a tiling of the plane is possible, but the tiling cannot be spatially periodic. In the examples known, it appears that the basic arrangement of tiles is always self-similar, so that it is almost periodic. In the simplest known examples, six square dominoes or just two irregularly shaped dominoes are required for this phenomenon to occur. (The simplest known example in three dimensions involves seven polyhedral ``dominoes.'')

The problem of whether a set of dominoes can tile a finite, say, region of the plane is clearly decidable, but is NP complete. The analogous problem of determining whether a particular patch can occur in an invariant configuration for a two-dimensional cellular automaton, or can in fact be generated by one time step of evolution from any initial state, is thus also NP complete. These problems can presumably be solved only by computations whose complication increases faster than a polynomial in , and are essentially equivalent to explicit testing of all possible cases.

In addition to considering configurations of site values generated at a particular step in the evolution of a cellular automaton, one may also discuss sequences of site values obtained with time. In general one may consider the number of possible arrangements of site values in a space-time volume consisting of a parallelepiped with generator vectors . The set entropy may than be defined as the exponential rate of increase of as the lengths of certain generators are taken to infinity (cf. Refs. 38 and 39):

where the are scalar parameters, and . These entropies are in fact functions of the unit forms obtained as the exterior products of the generator vectors considered as one-forms in space-time. Certain convergence properties of the limits in Eq. (4.3) can be proved from the fact that the number of arrangements of site values in a volume is submultiplicative, so that . A measure-theoretical analog of the set entropy (4.3) may be defined in correspondence with Eq. (4.2).

The spatial entropy (4.1) for two-dimensional cellular automata is obtained from the general definition (4.3) by choosing , and taking and to be orthogonal purely spacelike vectors along the two lattice directions. The generator vector is taken to be in the positive time direction, but the number of arrangements is independent of since a complete configuration at one time step determines all future configurations.

For a -dimensional cellular automaton, there are critical values of and such that entropies corresponding to higher or lower-dimensional parallelepipeds are zero or infinity. Entropies with exactly those critical values may be nonzero and bounded by quantities that depend on the cellular automaton neighborhood size.

Entropies are essentially determined by the correlations between values of sites at different space-time points. These correlations depend on the propagation of information in the cellular automaton. The difference patterns discussed in Section 3 provide measures of such information propagation. They can be considered as analogs of Green functions (cf. Ref. 4) which describe the change produced at some space-time point in a cellular automaton as a consequence changes at another point . The set-theoretical Green's function is defined to be nonzero whenever a change at in any configuration could lead to a change at . In the measure-theoretical Green's function the possible configurations are weighted with their probabilities. The maximum rate of information propagation is determined by the slope of the space-time (``light'') cone within which the Green's function is nonzero. The slope corresponding to propagation in a particular spatial direction in say a two-dimensional cellular automaton gives the Lyapunov exponent in that direction for the cellular automaton evolution. In most cases it appears that the space-time structure corresponding to the set of sites on which the Green's function is nonzero tends to a fixed form after rescaling at large times, so that the structure has a unique growth dimension, and the Lyapunov exponents have definite values. Exceptions may occur in rules where difference patterns spread along domain boundaries, typically producing asymptotically self-similar structures analogous to percolation clusters (e.g., Ref. 26).

The Green's functions describe not only how a change at some time affects site values at later times, but also how the value of a particular site is affected by the previous values of other sites. The backward light cone of a site contains all the sites whose values can affect it. (Notice that the backward light cone for a bijective rule in general has little relation with the forward light cone for the inverse rule.) The values of all sites in a volume are thus determined by the values of sites on a surface that ``absorbs'' (covers) all the backward light cones of points in . The number of possible configurations in is then bounded from above by the number of possible configurations of the set of sites within one cellular automaton neighborhood of the surface . The entropy associated with the volume is then not greater than the entropy associated with the volume around . By choosing various ``absorbing surfaces'' , whose sizes are determined by the rates of information propagation in different directions, one can derive various inequalities between entropies.

Many entropies can be defined for cellular automata using Eq. (4.3). One significant class is those that are invariant under continuous invertible transformations on the space of cellular automaton configurations. Such entropies can be used to identify topologically inequivalent cellular automaton rules. For one-dimensional cellular automata, an invariant entropy may be defined by taking , in Eq. (4.3), and choosing in the positive time direction, and in the space direction. The entropy may be generalized by taking the to be an arbitrary pair of orthogonal spacetime vectors (with having a positive time component). The most direct generalization of these invariant entropies to two-dimensional cellular automata would have , , and take the to be an orthogonal triple of space-time vectors with having a positive time component. If were chosen purely timelike, then this entropy would have no dependence on spatial direction, and would correspond to the standard invariant entropy defined for the cellular automaton mapping. In general however, there is no upper bound on its value, and it is apparently infinite for most cellular automata that have positive Lyapunov exponents in more than one spatial direction. A finite entropy can nevertheless be constructed by choosing . This entropy depends on the spatial (or in general space-time) vector . To obtain an invariant entropy, one must perform some average over this vector (accounting for the fact that the entropy is a homogeneous function of degree one in the length of the vector). One possibility is to form the integral of the quantity (4.3) over those values of the vector for which the quantity is less than some constant (say, 1).

previous  l  next