Information Propagation

Cellular automata may also be characterized by the stability or predictability of their behaviour under small perturbations in initial configurations. Figure 2 shows differences in patterns generated by cellular automata resulting from a change in a single initial site value. Such perturbations have characteristic effects on the four classes of cellular automata:

[ Figure 3 ] Evolution of various cellular automata from disordered initial states. In many cases, ordered structure is seen to be generated. The first row of pictures show examples of the four qualitative classes of behaviour found. (The rules shown are the same as in Fig. 1.) The lower two rows show examples of cellular automata with (five possible values for each site) and (nearest neighbour rules). Site values 0 to 4 are represented by white, red, green, blue and yellow squares, respectively. (The rules shown have totalistic codes 10175, 566780, 570090, 580020, 583330, 672900, 5694390, 59123000.) The `orange' discoloration is a background, not part of the pattern.

[ Figure 4 ] Evolution of multiple phases in cellular automata. Pairs of sites are shown combined: 00 is represented by white, 01 by red, 10 by green and 11 by blue. Alternate time steps are shown. Both rules simulate an additive rule(number 90) under a blocking transformation. In the first rule (number 18), the simulation is attractive: starting from a disordered initial state, the domains grow with time. In the second rule (number 94), the simulation is repulsive: only evolution from a special initial state yields additive rule behaviour: a defect is seen to grow, and attractive simulation of the identity rule takes over.

[ Figure 5 ] Examples of the evolution of a typical class 4 cellular automaton from disordered initial states. This and other class 4 cellular automata are conjectured to be capable of arbitrary information processing, or universal computation. The rule shown has , , and takes the value of a site to be 1 if the sum of the values of the sites in its three-site neighbourhood is 2 or 6, to be 2 if the sum is 3, and to zero otherwise (totalistic code 792).

[ Figure 6 ] Persistent structures generated in the evolution of the class 4 cellular automaton of Fig. 5. The first four structures shown have periods 1, 20, 16 and 12 respectively; the last four structures (and their reflections) propagate: the first has period 32, the next three period 3, and the last period 6. These structures are some of the elements required to support universal computation.

[ Figure 7 ] Evolution of some cellular automata with reversible rules. Each configuration is a unique function of the two previous configurations. (Rule numbers 4, 22, 90 and 126 are shown.) As initial conditions, each site in two successive configurations is chosen to have value 1 with probability 0.1.

1. no change in final state;
2. changes only in a finite region;
3. changes over an ever-increasing region;
4. irregular changes.

In class 1 and 2 cellular automata, information associated with site values in the initial state propagates only a finite distance; in class 3 cellular automata, it propagates an infinite distance at a fixed speed, while in class 4 cellular automata, it propagates irregularly but over an infinite range. The speed of information propagation is related to the Lyapunov exponent for the cellular automaton evolution, and measures the degree of sensitivity to initial conditions (see ref. [16]). It leads to different degrees of predictability for the outcome of cellular automaton evolution:

1. entirely predictable, independent of initial state;
2. local behaviour predictable from local initial state;
3. behaviour depends on an ever-increasing initial region;
4. behaviour effectively unpredictable.

Information propagation is particularly simple for the special class of additive cellular automata (whose local rule function is linear modulo ), in which patterns generated from arbitrary initial states may be obtained by superposition of patterns generated by evolution of simple initial states containing a single non-zero site. A rather complete algebraic analysis of such cellular automata may be given [17]. Most cellular automata are not additive; however, with special initial configurations it is often possible for them to behave just like additive rules. Thus, for example, the evolution of an initial configuration consisting of a sequence of 00 and 01 digrams under one rule may be identical to the evolution of the corresponding `blocked' configuration consisting of 0 and 1 under another rule. In this way, one rule may simulate another under a blocking transformation (analogous to a renormalization group transformation). Evolution from an arbitrary initial state may be attracted to (or repelled from) the special set of configurations for which such a simulation occurs. Often several phases exist, corresponding to different blocking transformations: sometimes phase boundaries move at constant speed, and one phase rapidly takes over; in other cases, phase boundaries execute random walks, annihilating in pairs, and leading to a slow increase in the average domain size, as illustrated in Fig. 4. Many rules appear to follow attractive simulation paths to additive rules, which correspond to fixed points of blocking transformations, and thus exhibit self similarity. The behaviour of many rules at large times, and on large spatial scales, is therefore determined by the behaviour of additive rules.

previous  l  next