5. Stability Properties

Section 4 considered properties of possible patterns generated by evolution with the cellular automaton rule of Eq. (3.1), starting from all possible initial configurations. This section considers the change in the patterns produced by small perturbations in the initial state. Figure 5.1 shows the differences resulting from reversal of a single site value in a typical disordered initial configuration. The region affected increases in size with time, reflecting the instability of the patterns generated.

This instability implies that information on localized changes eventually propagates throughout the cellular automaton. The rates of information transmission to the left and right are determined by the slopes of the difference pattern in Fig. 5.1. These in turn give left and right Lyapunov exponents and for the cellular automaton evolution [15, 26]. (The sequence of site values in a configuration, starting from a particular point, can be represented as a real number. Linear growth of the difference pattern in Fig. 5.1 then implies exponential divergence of the numbers representing nearby configurations.)

The form of the cellular automaton rule (3.1) immediately implies that

For consider a configuration in which the difference pattern has reached site . Whatever the current values of sites and , the in (3.1) leads to a change in the new value of site . The value (5.1) is the maximum allowed by the locality of the rule (3.1).

Empirical measurements suggest that the left-hand side of the difference pattern expands at an asymptotically linear rate, with a slope [45]

A simple statistical estimate for can be given. Consider a pair of configurations for which the front of the difference pattern has reached site . As a first approximation, one may assume that the motion of this front depends only on the neighbouring values and , where, by construction, is the same for the two configurations. When , the front advances (left) by one site, independent of the values of the . When , the front remains stationary if the for the two configurations are equal, and retreats by one site if they are unequal. If possible sets of site values occurred with equal probabilities, the front should thus follow a biased random walk, advancing at average speed . In practice, however, Fig. 5.1 shows that the front can retreat by many sites in a single time step. This occurs when the cellular automaton rule yields the same image for multiple site value sequences, as for say 10100 and 11001. Such phenomena make the probabilities for different difference patterns unequal, and invalidate this purely statistical approach discussed. (The values of obtained in this approach by considering the effects of between 1 and 5 sites on the right are 0.25, 0.1875, 0.15625, 0.140625 and 0.134766.)

[ Figure 5.1 ] Differences in patterns produced by evolution according to the cellular automaton rule of Eq. (3.1) from two typical disordered states which differ by reversal of the centre site value. The growth of the region of differences reflects the instability of the cellular automaton evolution.

The result (5.2) gives the average speed of the left-hand side of the difference pattern. As the random walk interpretation suggests, however, one can choose initial configurations for which a single site change leads to differences which expand at speed 1 on the left. In general, one can construct the analog of a Green's function, giving the probability that a site at a particular position and time will be affected by an initial perturbation. This function is nonzero within a ``light cone'' with edges expanding at speed 1. It appears to be uniform on the right-hand side. But on the left-hand side, it appears to be determined by a diffusion equation which gives the average behaviour of the biased random walk. The difference pattern can thus extend beyond the line given by Eq. (5.2), but with an exponentially damped probability.

Lyapunov exponents measure the rate of information transmission in cellular automata, and provide upper bounds on entropies, which measure the information content of patterns generated by cellular automaton evolution. For surjective cellular automata it can be shown, for example, that [15]

consistent with Eq. (4.6) and (5.2). The existence of positive Lyapunov exponents is a characteristic feature of class 3 cellular automata.

The difference pattern of Fig. 5.1, and the related Green's function, measure the effect of initial perturbations on the values of individual sites. In studying random sequence generation, one must also consider the effect of such perturbations on time sequences of site values, say of length . These sequences are always completely determined from the initial values of sites. But not all these initial values necessarily affect the time sequences. A change in any of the left-hand initial sites necessarily leads to a change in at least one element of the time sequence. But some changes in the right-hand initial sites have no effect on any element of the time sequence. It seems that the probability for a particular initial site to affect the time sequence decreases exponentially with distance to the right. The average number of sites on the right which affect the time sequence is found to be approximately . Thus the total number of initial sites on which a length time sequence depends is on average approximately . This result is presumably related to the entropy (4.6).

previous  l  next