Universality Classes in Cellular Automata

To proceed in analyzing universality in cellular automata, one must first give more quantitative definitions of the classes identified above. One approach to such definitions is to consider the degree of predictability of the outcome of cellular automaton evolution, given knowledge of the initial state. For class 1 cellular automata complete prediction is trivial: regardless of the initial state, the system always evolves to a unique homogeneous state. Class 2 cellular automata have the feature that the effects of particular site values propagate only a finite distance, that is, only to a finite number of neighboring sites. Thus a change in the value of a single initial site affects only a finite region of sites around it, even after an infinite number of time steps. This behavior, illustrated in Fig. 9, implies that prediction of a particular final site value requires knowledge of only a finite set of initial site values. In contrast, changes of initial site values in class 3 cellular automata, again as illustrated in Fig. 9, almost always propagate at a finite speed forever and therefore affect more and more distant sites as time goes on. The value of a particular site after many time steps thus depends on an ever-increasing number of initial site values. If the initial state is disordered, this dependence may lead to an apparently chaotic succession of values for a particular site. In class 3 cellular automata, therefore, prediction of the value of a site at infinite time would require knowledge of an infinite number of initial site values. Class 4 cellular automata are distinguished by an even greater degree of unpredictability, as discussed below.

[ Figure 9 ] Difference patterns showing the differences between configurations generated by evolution, according to various cellular automaton rules, from initial states that differ in the value of a single site. Each difference pattern is labeled by the behavior class of the cellular automaton rule. The effects of changes in a single site value depend on the behavior class of the rule: for class 2 rules the effects have finite range; for class 3 rules the effects propagate to neighboring sites indefinitely at a fixed speed; and for class 4 rules the effects also propagate to neighboring sites indefinitely but at various speeds. The difference patterns shown here are analogues of Green's functions for cellular automata.

Class 2 cellular automata may be considered as ``filters'' that select particular features of the initial state. For example, a class 2 cellular automata may be constructed in which initial sequences 111 survive, but sites not in such sequences eventually attain value 0. Such cellular automata are of practical importance for digital image processing: they may be used to select and enhance particular patterns of pixels. After a sufficiently long time any class 2 cellular automaton evolves to a state consisting of blocks containing nonzero sites separated by regions of zero sites. The blocks have a simple form, typically consisting of repetitions of particular site values or sequences of site values (such as 101010). The blocks either do not change with time (yielding vertical stripes in the patterns of Fig. 8) or cycle between a few states (yielding ``railroad track'' patterns).

While class 2 cellular automata evolve to give persistent structures with small periods, class 3 cellular automata exhibit chaotic aperiodic behavior, as shown in Fig. 8. Although chaotic, the patterns generated by class 3 cellular automata are not completely random. In fact, as mentioned for the example of Eq. 1, they may exhibit important self-organizing behavior. In addition and again in contrast to class 2 cellular automata, the statistical properties of the states generated by many time steps of class 3 cellular automaton evolution are the same for almost all possible initial states. The large-time behavior of a class 3 cellular automaton is therefore determined by these common statistical properties.

The configurations of an infinite cellular automaton consist of an infinite sequence of site values. These site values could be considered as digits in a real number, so that each complete configuration would correspond to a single real number. The topology of the real numbers is, however, not exactly the same as the natural one for the configurations (the binary numbers 0.111111 and 1.00000 are identical, but the corresponding configurations are not). Instead, the configurations of an infinite cellular automaton form a Cantor set. Figure 10 illustrates two constructions for a Cantor set. In construction (a) of Fig. 10, one starts with the set of real numbers in the interval 0 to 1. First one excludes the middle third of the interval, then the middle third of each interval remaining, and so on. In the limit the set consists of an infinite number of disconnected points. If positions in the interval are represented by ternimals (base 3 fractions, analogous to base 10 decimals), then the construction is seen to retain only points whose positions are represented by ternimals containing no 1's (the point 0.2202022 is therefore included; 0.2201022 is excluded). An important feature of the limiting set is its self-similarity or fractal form: a piece of the set, when magnified, is indistinguishable from the whole. This self-similarity is mathematically analogous to that found for the limiting two-dimensional pattern of Fig. 3.

In construction (b) of Fig. 10, the Cantor set is formed from the ``leaves'' of an infinite binary tree. Each point in the set is reached by a unique path from the ``root'' (top as drawn) of the tree. This path is specified by an infinite sequence of binary digits, in which successive digits determine whether the left- or right-hand branch is taken at each successive level in the tree. Each point in the Cantor set corresponds uniquely to one infinite sequence of digits and thus to one configuration of an infinite cellular automaton. Evolution of the cellular automaton then corresponds to iterated mappings of the Cantor set to itself. (The locality of cellular automaton rules implies that the mappings are continuous.) This interpretation of cellular automata leads to analogies with the theory of iterated mappings of intervals of the real line. (See Mitchell J. Feigenbaum, ``Universal Behavior in Nonlinear Systems,'' Los Alamos Science, Vol. 1, No. 1(1980): 4--27.)

Cantor sets are parameterized by their ``dimensions.'' A convenient definition of dimension, based on construction (a) of Fig. 10, is as follows. Divide the interval from 0 to 1 into bins, each of width . Then let be the number of these bins that contain points in the set. For large this number behaves according to

and is defined as the ``set dimension'' of the Cantor set. If a set contained all points in the interval 0 to 1, then with this definition its dimension would simply be 1. Similarly, any finite number of segments of the real line would form a set with dimension 1. However, the Cantor set of construction (a), which contains an infinite number of disconnected pieces, has a dimension according to Eq. 2 of .

[ Figure 10 ] Steps in two constructions of a Cantor set. At each step in construction (a), the middle third of all intervals is excluded. The first step thus excludes all points whose positions, when expressed as base 3 fractions, have a 1 in the first ``ternimal place'' (by analogy with decimal place), the second step excludes all points whose positions have a 1 in the second ternimal place, and so on. The limiting set obtained after an infinite number of steps consists of an infinite number of disconnected points whose positions contain no 1's. The set may be assigned a dimension, according to Eq. 2, that equals . Construction (b) reflects the topological structure of the Cantor set. Infinite sequences of digits, representing cellular automaton configurations, are seen to correspond uniquely with points in the Cantor set.

An alternative definition of dimension, agreeing with the previous one for present purposes, is based on self-similarity. Take the Cantor set of construction (a) in Fig. 10. Contract the set by a magnification factor . By virtue of its self-similarity, the whole set is identical to a number, say , of copies of this contracted copy. For large , , where again is defined as the set dimension.

With these definitions the dimension of the Cantor set of all possible configurations for an infinite one-dimensional cellular automaton is 1. A disordered ensemble, in which each possible configuration occurs with equal probability, thus has dimension 1. Figure 11 shows the behavior of the probabilities for the configurations of a typical cellular automaton as a function of time, starting from such a disordered initial ensemble. As expected from the irreversibility of cellular automaton evolution, exemplified by the state transition graph of Fig. 6, different configurations attain different probabilities as evolution proceeds, and the probabilities for some configurations decrease to zero. This phenomenon is manifest in the ``thinning'' of configurations on successive time steps apparent in Fig. 11. The set of configurations that survive with nonzero probabilities after many time steps of cellular automaton evolution constitutes the ``attractors'' for the evolution. This set is again a Cantor set; for the example of Fig. 11 its dimension is , where is the real solution of the polynomial equation . (See D. A. Lind, ``Applications of Ergodic Theory and Sofic Systems to Cellular Automata,'' University of Washington preprint (April 1983) and to be published in Physica D; see also Martin et al., op. cit.) The greater the irreversibility in the cellular automaton evolution, the smaller is the dimension of the Cantor set corresponding to the attractors for the evolution. If the set of attractors for a cellular automaton has dimension 1, then essentially all the configurations of the cellular automaton may occur at large times. If the attractor set has dimension less than 1, then a vanishingly small fraction of all possible configurations are generated after many time steps of evolution. The attractor sets for most class 3 cellular automata have dimensions less than 1. For those class 3 cellular automata that generate regular patterns, the more regular the pattern, the smaller is the dimension of the attractor set; these cellular automata are more irreversible and are therefore capable of a higher degree of self-organization.

[ Figure 11 ] Time evolution of the probabilities for each of the 1024 possible configurations of a typical class 3 cellular automaton with and and of size 10, starting from an initial ensemble in which each possible configuration occurs with equal probability. The configurations are specified by integers whose binary digits form the sequence of site values. The probability for a particular configuration is given on successive lines in a vertical column: a dot appears at a particular time step if the configuration occurs with nonzero probability at that time step. In the initial ensemble all configurations occur with equal nonzero probabilities, and dots appear in all positions. The cellular automaton evolution modifies the probabilities for the configurations, making some occur with zero probability and yielding gaps in which no dots appear. This ``thinning'' is a consequence of the irreversibility of the cellular automaton evolution and is reflected in a decrease of entropy with time. In the limit of cellular automata of infinite size, the configurations appearing at large times form a Cantor set. For the rule shown (rule 18 in the notation of Fig. 7) the limiting dimension of this Cantor set is found to be approximately 0.88.

The dimension of a set of cellular automaton configurations is directly proportional to the limiting entropy (or information) per site of the sequence of site values that make up the configurations. (See Patrick Billingsley, Ergodic Theory and Information, John Wiley & Sons, 1965.) If the dimension of the set was 1, so that all possible sequences of site values could occur, then the entropy of these sequences would be maximal. Dimensions lower than 1 correspond to sets in which some sequences of site values are absent, so that the entropy is reduced. Thus the dimension of the attractor for a cellular automaton is directly related to the limiting entropy attained in its evolution, starting from a disordered ensemble of initial states.

Dimension gives only a very coarse measure of the structure of the set of configurations reached at large times in a cellular automaton. Formal language theory may provide a more complete characterization of the set. ``Languages'' consist of a set of words, typically infinite in number, formed from a sequence of letters according to certain grammatical rules. Cellular automaton configurations are analogous to words in a formal language whose letters are the possible values of each cellular automaton site. A grammar then gives a succinct specification for a set of cellular automaton configurations.

Languages may be classified according to the complexity of the machines or computers necessary to generate them. A simple class of languages specified by ``regular grammars'' may be generated by finite state machines. A finite state machine is represented by a state transition graph (analogous to the state transition graph for a finite cellular automaton illustrated in Fig. 6). The possible words in a regular grammar are generated by traversing all possible paths in the state transition graph. These words may be specified by ``regular expressions'' consisting of finite length sequences and arbitrary repetitions of these. For example, the regular expression represents all sequences containing an even number of 0's (arbitrary repetition of the sequence ) flanked by a pair of 1's. The set of configurations obtained at large times in class 2 cellular automata is found to form a regular language. It is likely that attractors for other classes of cellular automata correspond to more complicated languages.

previous  l  next