6. Class 2 Cellular Automata

Class 2 cellular automata serve as ``filters'' which generate separated simple structures from particular (typically short) initial site value sequences. (4) The density of appropriate sequences in a particular initial state therefore determines the statistical properties of the final state into which it evolves. (There is therefore no unique large-time (invariant) probability measure on the set of possible configurations.) Changes of site values in the initial state almost always affect final site values only within a finite range, typically of order . The maximum average propagation speed defined in section 4 thus vanishes for class 2 cellular automata. The temporal and mapping (but not spatial) dimensions for such automata therefore also vanish.

Although for all class 2 cellular automata, is often nonzero. Thus exceptional initial states may exist, from which, for example, unbounded growth may occur. Such initial states apparently occur with probability zero for ensembles of (spatially infinite) cellular automata with smooth probability measures.

The simple structures generated by class 2 cellular automata are either stable, or are periodic, typically with small periods. The class 2 rules with codes 8, 24, 40 and 56 illustrated in fig. 1 all apparently exhibit only stable persistent structures. Examples of class 2 cellular automata which yield periodic, rather than stable, persistent structures include the , cellular automaton with rule number 108 [1], and the , totalistic cellular automaton with code 198. The periods of persistent structures generated in the evolution of class 2 cellular automata are usually less than . However, examples have been found with larger periods. One is the , totalistic cellular automata with code 228, in which a persistent structure with period 3 is generated.

The finiteness of the periods obtained at large times in class 2 cellular automata implies that such systems have , as deduced above from the vanishing of . The evolution of class 2 cellular automata to zero (temporal) dimension attractors is analogous to the evolution of some continuous dynamical systems to limit cycles.

The set of persistent structures generated by a given class 2 cellular automaton is typically quite simple. For some rules, there are only a finite number of persistent structures. For example, for the code 8 and code 40 rules of fig. 1, only the sequence (surrounded by 0 sites) appears to be persistent. For code 24, and are both persistent. Other rules yield an infinite sequence of persistent structures, typically constructed by a simple process. For example, with code 56 in fig. 1, any sequence of two or more consecutive sites is persistent.

In general, it appears that the set of persistent structures generated by any class 2 cellular automaton corresponds to the set of words generated by a regular grammar. A regular grammar [15], [16], [17] and [18] (or ``sofic system'' [19]) specifies a regular language, whose legal words may be recognized by a finite automaton, represented by a finite state transition graph. A sequence of symbols (site values) specifies a particular traversal of the state transition graph. The traversal begins at a special ``start'' node; the symbol sequence represents a legal word only if the traversal does not end at an absorbing ``stop'' node. Each successive symbol in the sequence causes the automaton to make a transition from one state (node) to one of others, as specified by the state transition graph. At each step, the next state of the automaton depends only on its current state, and the current symbol read, but not on its previous history.

The set of configurations (symbol sequences) generated from all possible initial configurations by one time step of cellular automaton evolution may always be specified by a regular grammar. To determine whether a particular configuration may be generated after one time step of cellular automaton evolution, one may attempt to construct an explicit predecessor for it. Assume that a predecessor configuration has been found which reproduces all site values up to position . Definite values for all are then determined. Several of the total of sequences of values may be possible. Each sequence may be specified by an integer . An integer between 0 and may then be defined, with the th binary bit in equal to one if sequence is allowed, and 0 otherwise. Each possible value of may be considered to correspond to a state in a finite automaton. corresponds to a ``stop'' state, which is reached if and only if has no predecessors. Possible values for are then found from and the value of . These possible values then determine the value of . A finite state transition graph, determined by the cellular automaton rules, gives the possible transitions . Configurations reached after one time step of cellular automaton evolution may thus be recognized by a finite automaton with at most states. The set of such configurations is thus specified by a regular grammar.

In general, if the value of a given site after steps of cellular automaton evolution depends on initial site values, then the set of configurations generated by this evolution may be recognized by a finite automaton with at most states. The value of may increase as , potentially requiring an infinite number of states in the recognizing automaton, and preventing the specification of the set of possible configurations by a regular grammar. However, as discussed above, the value of for a class 2 cellular automaton apparently remains finite as . Thus the set of configurations which may persist in such a cellular automaton may be recognized by a finite automaton, and are therefore specified by a regular grammar. The complexity of this grammar (measured by the minimum number of states required in the state transition graph for the recognizing automaton) may be used to characterize the complexity of the large time behaviour of the cellular automaton.

Finite class 2 cellular automata usually evolve to short period cycles containing the same persistent structures as are found in the infinite case. The fraction of exceptional initial states yielding other structures decreases rapidly to zero as increases.

previous  l  next