7. Class 3 Cellular Automata

Evolution of infinite class 3 cellular automata from almost all possible initial states leads to aperiodic (``chaotic'') patterns. After sufficiently many time steps, the statistical properties of these patterns are typically the same for almost all initial states. In particular, the density of nonzero sites typically tends to a fixed nonzero value (often close to ). In infinite cellular automata, ``equilibrium'' values of statistical quantities are approached roughly exponentially with time, and are typically attained to high accuracy after a very few time steps. For a few rules (such as the , rule with rule number 18 [20]), however, ``defects'' consisting of small groups of sites may exist, and may execute approximate random walks, until annihilating, usually in pairs. Such processes lead to transients which decrease with time only as .

Figure 1 showed examples of the patterns generated by evolution of some typical class 3 cellular automata from disordered initial states. The patterns range from highly irregular (as for code 10), to rather regular (as for code 12). The most obvious regularity is the appearance of large triangular ``clearings'' in which all sites have the same value. These clearings occur when a ``fluctuation'' in which a sequence of consequence of consecutive sites have the same value, is progressively destroyed by the effects of other sites. The rate at which ``information'' from other sites may ``flow'' into the fluctuation, and thus the slope of the boundaries of the clearing, may range from to sites per time step. The qualitative regularity of patterns generated by some class 3 rules arises from the high density of long sequences of correlated site values, and thus of triangular clearings. In general, however, it appears that the density of clearings decreases with their size roughly as . Different cellular automata appear to yield a continuous range of values. Those with larger yield more regular patterns, while those with smaller yield more irregular patterns. No sharp distinction appears to exist between class 3 cellular automata yielding regular and irregular patterns.

The first column of fig. 9 shows patterns obtained by evolution with typical class 3 cellular automaton rules from initial states containing a single nonzero site. Unbounded growth, leading to an asymptotically infinite number of nonzero sites, is evident in all cases. Some rules are seen to give highly regular patterns, others lead to irregular patterns.

The regular patterns obtained with rules such as code 2 are asymptotically self-similar fractal curves (cf. [11]). Their form is identical when viewed at different magnifications, down to length scales of order sites. The total number of nonzero sites in such patterns after time steps approaches , where gives the fractal dimension of the pattern. Many class 3 rules generate a similar pattern, illustrated by codes 2 and 34 in fig. 9, with . Some rules yield self-similar patterns with other fractal dimensions (for example, code 38 yields ), but all self-similar patterns have , and lead to an asymptotic density of sites which tends to zero as .

[ Figure 9 ] Evolution of some class 3 totalistic cellular automata with and (as illustrated in fig. 1) from initial states containing one or a few nonzero sites. Some cases yield asymptotically self-similar patterns, while others are seen to give irregular patterns.

Rules such as code 10 are seen to generate irregular patterns by evolution even from a single site initial state. The density of nonzero sites in such patterns is found to tend asymptotically to a nonzero value; in some, but not all, cases the value is the same as would be obtained by evolution from a disordered initial state. The patterns appear to exhibit no large-scale structure.

Cellular automata contain no intrinsic scale beyond the size of neighbourhood which appears in their rules. A configuration containing a single nonzero site is also scale invariant, and any pattern obtained by evolution from it with cellular automaton rules must be scale invariant. The regular patterns in fig. 9 achieve this scale invariance by their self-similarity. The irregular patterns presumably exhibit correlations only over a finite range, and are therefore effectively uniform and scale invariant at large distances.

The second and third columns in fig. 11 show the evolution of several typical class 3 cellular automata from initial states with nonzero sites in a small region. In some cases (such as code 12), the regular fractal patterns obtained with single nonzero sites are stable under addition of further nonzero initial sites. In other cases (such as code 2) they are seen to be unstable. The numbers of rules yielding stable and unstable fractal patterns are found to be roughly comparable.

Many but not all rules which evolve to regular fractal patterns from simple initial states generate more regular patterns in evolution from disordered initial states. Similarly, many but not all rules which produce stable fractal patterns yield more regular patterns from disordered initial states. For example, code 42 in figs. 1 and 9 generates stable fractal patterns from a simple initial state, but leads to an irregular pattern under evolution from a disordered state. (Although not necessary for such behaviour, this rule possesses the additivity property mentioned in section 2.)

The methods of section 4 may be used to analyse the general behaviour of class 3 cellular automata evolving from typical initial states, in which all sites have nonzero values with nonzero probability. Class 3 cellular automata apparently always exhibit a nonzero minimum average propagation speed . Small changes in initial states thus almost always lead to increasingly large changes in later states. This suggests that both spatial and temporal dimensions and should be nonzero for all class 3 cellular automata. These dimensions are determined according to eqs. (4.15), (4.18), (4.22) and (4.23) by the limiting values of spatial and temporal entropies.

A disordered or statistically random initial state, in which each site takes on its possible values with equal independent probabilities, has maximal spatial entropy for all block lengths . Figure 10 shows the behaviour of as a function of time for several block lengths in the evolution of a typical class 3 cellular automaton from a disordered (maximal entropy) initial state. The entropies are seen to decrease for a few time steps, and then to reach ``equilibrium'' values. The ``equilibrium'' values of for class 3 cellular automata are typically independent of the probability measure on the ensemble of possible initial states, at least for ``smooth'' measures. The decrease in entropy with time manifests the irreversible nature of the cellular automaton evolution. The decrease is found to be much greater for class 3 cellular automata which generate regular patterns (with many triangular clearings) than for those which yield irregular patterns. The more regular patterns require a higher degree of self-organization, with correspondingly greater irreversibility, and larger entropy decrease.

[ Figure 10 ] Evolution of spatial measure entropies as a function of time for evolution of the class 3 cellular automaton with code 12 illustrated in fig. 1 from a disordered initial state. The irreversibility of cellular automaton evolution results in a decrease of the entropies with time. Rapid relaxation to an ``equilibrium'' state is nevertheless seen.

[ Figure 11 ] Evolution of (a) spatial and (b) temporal measure entropies and obtained at equilibrium by evolution of several class 3 cellular automata illustrated in fig. 1, as a function of the spatial and temporal block lengths and . The entropies are evaluated for the regions indicated in figs. 7(a) and 7(b). The limit of as is the spatial measure dimension of the attractor for the system; the limit of as is the temporal measure dimension.

As discussed in section 4, the dependence of on measures spatial correlations in cellular automaton configurations. therefore tends to a constant if is larger than the range of any correlations between site values. In the presence of correlations, always decreases with . Available data from simulations provide reliable accurate estimates for only for . Figure 11 shows the behaviour of the equilibrium value of as a function of over this range for several typical class 3 cellular automata. For rules which yield irregular patterns the equilibrium value of typically remains for . at equilibrium typically decreases much more rapidly for class 3 cellular automata which generate more regular patterns. At least for small , for such cellular automata typically decreases roughly as with .

The values of the spatial set entropy provide upper bounds on the spatial measure entropy . The distribution of nonzero probabilities for possible length blocks is typically quite broad, yielding an significantly smaller than . Nevertheless, the general behaviour of with usually roughly follows , but with a slight delay.

As discussed in section 4, the set entropy attains its maximum value of 1 if and only if all sequences of length appear (with nonzero probability) in evolution from some initial state. Notice that if after one time step, then at any time. In general, takes on value 1 for blocks up to some critical length (perhaps infinite), as defined in eq. (4.13).

Since a block of length is completely determined by a sequence of length in the previous configuration, any predecessors for the block may in principle be found by an exhaustive search of all possible length sequences. The procedure for progressive construction of predecessors outlined in section 6 provides a more efficient procedure [21]. The critical block length is determined by the minimum number of nodes in the finite automaton state transition graph visited on any path from the ``start'' to ``stop'' node. The state transition graph is determined by the set of transition rules . Starting with length 1 blocks, these transition rules may be found by considering construction of all possible progressively longer blocks, but ignoring blocks associated with values for which the transition rules have already been found. If is finite, the ``stop'' node is reached in the construction of length blocks. Alternatively, the state transition graph may be found to consist of closed cycles, not including . In this case, is determined to be infinite. Since the state transition graph contains at most nodes, the value of may be found after at most this many tests. The procedure thus provides a finite algorithm for determining whether all possible arbitrarily long sequences of site values may be generated by evolution with a particular cellular automaton rule.

Table 2 gives the critical block lengths for the cellular automata illustrated in fig. 1. Class 3 cellular automata with smaller tend to generate more regular patterns. Those with larger presumably give systematically larger entropies and their evolution is correspondingly less irreversible.

For additive cellular automata (such as code 42 in fig. 1 and table 2), all possible blocks of any length may be reached, and have exactly predecessors of length . In this case, therefore, evolution from a disordered initial state gives for all (hence ). The equality of the number of predecessors for each block implies in addition in this case that , at least for evolution from disordered initial states. Hence for additive cellular automata

The configurations generated by additive cellular automata are thus maximally chaotic.

In general cellular automata evolving according to eq. (2.1) yield for all , so that , if is an injective (one-to-one) function of either its first or last argument (or can be obtained by composition of functions with such a property). This may be proved by induction. Assume that all blocks of length are reachable, with predecessors of lengths . Then form a block of length by adding a site at one end. To obtain all possible length blocks, the value of this additional site must range over possibilities. Any predecessors for length blocks must be obtained by adding a -th site (with value ) at one end. For all length blocks to be reachable, all values of must be generated when runs over its possible values, and the result follows. Notice that not all length blocks need have the same (nonzero) number of predecessors, so that the measure entropy may be less than the set entropy .

[ Table 2 ] Values of critical block length for legal totalistic , cellular automata as illustrated in fig. 1. For , all possible blocks of site values appear with nonzero probability in configurations generated after any number of time steps in evolution from disordered initial states, while for , some blocks are absent, so that the spatial set entropy .

While injectivity of the rule function for a cellular automaton in its first or last arguments is sufficient to give , it is apparently not necessary. A necessary condition is not known.

In section 6 it was shown that the set of configurations obtained by cellular automaton evolution for a finite number of time steps from any initial state could be specified by a regular grammar. In general the complexity of the grammar may increase rapidly with the number of time steps, potentially leading at infinite time to a set not specifiable by a regular grammar. Such behaviour may generically be expected in class 3 cellular automata, for which the average minimum propagation speed .

As discussed in section 4, one may consider the statistics of temporal as well as spatial sequences of site values. The temporal aperiodicity of the patterns generated by evolution of class 3 cellular automata from almost all initial states suggests that these systems should have nonvanishing temporal entropies and nonvanishing temporal dimensions . Once again, the temporal entropies for blocks starting at progressively later times quickly relax to equilibrium values. Notice that the dimension obtained from the large limit of the is always independent of the starting times for the blocks. This is to be contrasted with the spatial dimensions , which depend on the time at which they are evaluated. Just as for spatial entropies, it found that the equilibrium temporal entropies are essentially independent of probability measure for initial configurations.

The temporal entropies decrease slowly with . In fact, it appears that in all cases

The ratio is, however, typically much smaller than its maximum value (4.38) equal to the maximum propagation speed . Notice that the value of determines the slopes of the edges of triangular clearings in the patterns generated by cellular automaton evolution.

At least for the class 3 cellular automata in fig. 1 which generate irregular patterns, the equilibrium set entropy for all for which data are available. Note that the result holds for all for any additive cellular automaton rule. One may speculate that class 3 cellular automata which generate apparently irregular patterns form a special subclass, characterized by temporal dimension .

For class 3 cellular automata which generate more regular patterns, appears to decrease, albeit slowly, with . Just as for spatial sequences, one may consider whether the temporal sequences which appear form a set described by a regular grammar. For the particular case of the , cellular automaton with rule number 18, there is some evidence [21] that all possible temporal sequences which contain no 11 subsequences may appear, so that where is the th Fibonacci number . This implies that for large , suggesting a temporal set dimension . In general, however, the set of possible temporal sequences is not expected to be described by a regular grammar.

The nonvanishing value of the average minimum propagation speed for class 3 cellular automata suggests that in all cases the value of a particular site depends on an ever-increasing number of initial site values. However, the complexity of this dependence is not known. The value of a site after time steps can always be specified by a table with an entry for each of relevant initial sequences. Nevertheless, it is possible that a finite state automaton, specified by a finite state transition graph, could determine the values of sites at any time.

The behaviour of finite class 3 cellular automata with additive rules was analysed in some detail in ref. 2. It was shown there that the maximal cycle length for additive cellular automata grows on average exponentially with the size of the cellular automaton. Most cycles were found to have maximal length, and the number of distinct cycles was found also to grow on average exponentially with . The lengths of transients leading to cycles was found to grow at most linearly with . The fraction of states on cycles was found on average to tend to a finite limit.

For most class 3 cellular automata, the average cycle length grows quite slowly with , although in some cases, the absolute maximum cycle length appears to grow rapidly. The lengths of transients are typically short for cellular automata which generate more regular patterns, but often become very long as increases for cellular automata which generate more irregular patterns. The fractions of states on cycles are typically much larger for finite class 3 cellular automata which generate irregular patterns than for those which generate more regular patterns. This is presumably a reflection of the lower irreversibility and larger attractor dimension found for the former case in the infinite size limit.

previous  l  next