4. Global Properties

This section considers the behaviour of the cellular automaton (3.1) starting from all possible initial states. The basic approach is to count the possible sequences and patterns that can occur, and to characterize them using methods from dynamical systems theory (e.g., [23]). The next section discusses the behaviour obtained by evolution from particular initial configurations. For purposes of simplicity, this section concentrates on the infinite size limit; Section 9 considers finite size effects.

Figure 4.1 shows a spacetime pattern produced by evolution according to (3.1) starting from a typical disordered initial state. While definite structure is evident, one may suspect that a single line of sites at any angle in the pattern can have an arbitrary sequence of values. Below we shall show that this is in fact the case: given an appropriate initial condition, any sequence can be generated in an infinite cellular automaton with the rule (3.1).

[ Figure 4.1 ] Pattern produced by evolution according to the cellular automaton rule (3.1) from a typical disordered initial state.

The rule (3.1) can be considered as a mapping from one (say infinite) cellular automaton configuration to another. An important property of this mapping is that it is surjective or onto. Any configuration can thus always be obtained as the image of some configuration , according to . A possible configuration (not necessarily unique) can be found by starting with a candidate pair of site values, then extending to the left using Eq. (3.3). So if all possible initial configurations are considered, then any configuration can be generated at any time step. Thus with appropriate initial conditions, any spatial sequence of site values can be produced.

Every length spatial sequence of site values that occurs is determined by a length sequence on the previous time step. The surjectivity of the rule (3.1) implies that such a predecessor exists for any length sequence. But Eq. (3.3) also implies that there are exactly four predecessors for any sequence. Given values , , and so on, in one sequence, the values and in its predecessor can be chosen in all the four possible ways; in each case the remaining are then uniquely determined by Eq. (3.3). Thus starting from an ensemble that contains all possible (infinite) cellular automaton configurations with equal probabilities, each configuration will be generated with equal probability throughout the evolution of the cellular automaton, and so every possible spatial sequence of a particular length will occur with equal frequency.

One may also consider sequences of values attained by a single site as a function of time. Starting from an initial ensemble which contains all configurations with equal probabilities, all such sequences again occur with equal frequencies. For, given any temporal sequence, iteration of Eq. (3.3) yields an equal number of initial configurations which evolve to it. The same is true for sequences of site values on lines at any angle in the spacetime pattern.

Entropies provide characterizations of the number of possible sequences that occur. First, let the number of distinct length blocks in these sequences be , and let the th such sequence appear with probability . Then the topological entropy of the sequence is given by (e.g., [15])

and the measure entropy by

If the cellular automaton configurations are considered as elements of a Cantor set, then these entropies give respectively the Hausdorff (strictly Kolmogorov) and measure dimensions of this set. If the sequences are considered as ''messages,'' then the entropies give respectively their capacity and Shannon information content.

For the cellular automaton of Eq. (3.1), all possible sequences occur with equal probabilities (given an equal probability initial ensemble) so both entropies are maximal:

Any reduction in entropy would reveal redundancy in the sequences, and would imply a lack of randomness. Equation (4.3) is thus a necessary (though not sufficient) condition for randomness. (It is related to statistical test of Section 10 and Appendix A.)

Although Eq. (4.3) implies that all possible sequences of values for single sites can occur along any spacetime direction, the deterministic nature of the cellular automaton rule (3.1) implies that only certain spacetime patches of values can occur. In fact, all the site values in a particular patch are completely determined by the values that appear on its upper, left and right boundaries. Once these boundaries are specified, the values of remaining sites in the patch are redundant, and can be found simply by applying (3.1) and (3.3).

In general the degree of redundancy in such spacetime patterns can be characterized by the invariant topological and measure entropies for the cellular automaton mapping, given by (e.g., [15, 24])

and

where gives the total number of distinct spacetime patches of site values that occur, and the give their probabilities.

It is clear from the locality of the rule (3.1) that

A calculation based on the method of [25] in fact shows that (3)

Hence a knowledge of the time sequences of values of about 1.2 sites suffice in principle to determine the values of all other sites. In practice however the function which gives the initial configuration in terms of these temporal sequences seems rapidly to become intractably complicated, as discussed in Section 7.

previous  l  next