5. Some Invariant Sets

Section 2 showed that the set of configurations generated after a finite number of steps in the evolution of any cellular automaton forms a regular language. Sections 3 and 4 discussed some properties of such sets. This section and the next one consider the limiting sets of configurations generated after many time steps of cellular automaton evolution.

For all configurations that appear in the limit set for a cellular automaton, there must exist some configuration such that for any . Any set of configurations invariant under the cellular automaton rule therefore appear in its limit set. This section considers some simple examples of invariant sets; Sect. 6 gives some comments on the complete structure of limit sets for cellular automata.

Periodic Sets

A simple class of invariant sets consist of configurations periodic with time under cellular automaton evolution. Such sets are found to form finite complement languages.

Consider the set of configurations that are stable (have temporal period 1) under a cellular automaton rule with and . The set of such configurations is exactly those which contain only neighbourhoods for which

Only the finite set of distinct three-site blocks that violate (5.1) are forbidden, so that the complete set forms a finite-complement language, with a maximum distinct excluded block of length 3. A NDFA that generates the set of stable configurations is represented by a graph analogous to Fig. 3.1 in which only those arcs satisfying (5.1) are retained. The minimal grammar for this set is obtained by constructing the minimal equivalent DFA, as described in Sect. 2.

The procedure generalizes immediately to arbitrary cellular automaton rules, and to sets of configurations with any finite period (cf. [37]). The distinct excluded blocks in the finite complement languages corresponding to sets of configurations with period have maximum length .

Figure 5.1 shows the minimal grammars for sets of configurations with various periods under the , cellular automata with rule numbers 90, 18 and 22. The grammars are represented by graphs containing several disconnected pieces, each corresponding to a disjoint set of configurations.

Figure 5.1a suggests that only a finite number of configurations, all spatially periodic, are found with each temporal period in the surjective cellular automaton rule 90. For this and other surjective cellular automata whose local mappings are injective in their first and last arguments, the number of distinct configurations with any period is always finite, and is exactly , where is the invariant entropy of the cellular automaton mapping ( for rule 90) (13).This result follows from the fact that the complete space-time pattern generated by the evolution of such a cellular automaton is completely determined by any patch of site values with infinite temporal extent, but spatial width (typically equal to ). Moreover, any possible set of site values may occur in this patch. If the complete space-time pattern is to have period , then so must the patch; but there are exactly possible patches with period . (For large , this result is as expected for any expansive homeomorphism (e.g. [10, 11]).)

In general, the sets of configurations with a particular periodicity under a cellular automaton rule are infinite, as illustrated for rules 18 and 22 in Figs. 5.1b and 5.1c. Presumably there are sets of this kind with arbitrarily large periods. These infinite sets are nevertheless finite complement languages. For example, for the set of configurations with period two under rule 18, only the distinct blocks 111, 1011, 1101 and 10101 are excluded. It is common in class 3 cellular automata to find configurations with almost every possible period; for class 4 cellular automata, only some periods are typically found.

[ Figure 5.1 ] Minimal deterministic finite automata corresponding to sets of configurations with (temporal) periods exactly under cellular automaton rules a 90, b 18 and c 22.

Periodic configurations form a small subset of all the configurations in the limit sets for cellular automata. Their entropy nevertheless provides a lower bound on the entropy of the complete limit sets. For rule 90, the set of periodic configurations has zero entropy, yet the complete limit contains all possible configurations, and thus has entropy 1. For rule 18, the period 2 set has entropy (given as the logarithm of the largest root of ), while the period 4 set has entropy (). For rule number 22, the period 4 set has entropy (). Since irreversible cellular automaton mappings are contractive, the entropy of the set obtained after a finite number of time steps gives an upper bound on the entropy of the complete limit set. Using results from Table 3.3 one then finds

Simulation Sets

The complete invariant sets for many cellular automata are very complicated. Parts of these invariant sets may however have a simpler structure, and may consist of configurations for which ``simulates'' a simpler cellular automaton rule. Thus for example stable configurations under may be considered as those for which ``simulates'' the identity mapping.

One class of configurations for which a cellular automaton rule may simulate a rule are those obtained by ``blocking transformations.'' Each symbol in the possible configurations of is replaced by a length block of symbols in , and each time step in the evolution of is simulated by time steps of evolution under . Thus, for example, rule 18 simulates rule 90 under the blocking transformation , [1, 38, 5]. The evolution of an arbitrary configuration under rule 90 is thus simulated by the evolution under rule 18 of a configuration consisting of the digrams 00 and 01. But since rule 90 is surjective, all possible configurations correspond to an invariant set. Thus configurations containing only 00 and 01 digrams form an invariant set for rule 18. The entropy of these configurations is , so that

Rule 22 simulates rule 90 under the blocking transformation , , implying that

A cellular automaton rule may simulate other rules with the same values of and under different blocking transformations (cf. the simulation network given in [5]). Some rules, apparently only surjective ones such as rule 90, simulate themselves, and thus correspond to fixed points of the blocking transformation. In other cases, one rule may simulate another under several distinct blocking transformations. For example, rule 18 simulates rule 90 under both , , and , , while rule 22 simulates rule 90 under any permutation of , . One may consider the sets of blocks appearing in these blocking transformations to represent different ``phases.'' An initial configuration then consists of several ``domains,'' each of which contains blocks of one phase. The domains are separated by ``walls.'' For rule 18, these walls appear to execute random walks, and annihilate in pairs, yielding progressively larger domains of a single phase [38]. The simulation of rule 90 by rule 18 may thus be considered ``attractive'' [3]. For rule 22, no such simple behaviour is observed.

Blocking transformations yield a particular class of configurations, corresponding to simple finite complement languages. Other classes of configurations, specified by more general grammars, may also yield simulations. (An example occurs for rule number 73, in which configurations containing only odd-length sequences of 0 and 1 sites simulate rule 90.) In addition, a set of configurations evolving under one rule may simulate an invariant set of configurations evolving under another rule.

previous  l  next