|
Articles Cellular Automata Computation Theory of Cellular Automata (1984)
Computation Theory of Cellular Automata (1984) |
|
Tables 3.1--3.3 gave several properties of the sets of configurations generated by a finite number of steps in the evolution of legal 
, 
cellular automata. This section discusses these results, identifies several types of behaviour, and considers analogies with classes of cellular automaton behaviour defined by dynamical systems theory means [2].
In the simplest cases, the set 
generated by a cellular automaton evolves to a fixed form after a small number of time steps 
(the case of surjective cellular automata, with 
for all 
, is considered separately). The minimal DFA corresponding to for all 
are then identical, and the values of 
and 
are thus constant. (Notice that 
does not necessarily imply 
, as seen for rule 36 in Table 3.1.) In addition, for , no more distinct blocks of sites are excluded. Such behaviour occurs in the trivial case of rule 0, under which all initial configurations are mapped to the null configuration after one time step. It also occurs for many other rules: one example is rule 76, discussed in Sects. 2 and 3. All the examples of this behaviour in Tables 3.1--3.3 have 
(e.g. rule 76) or 
(e.g. rule 108). In the trivial case of rule 0, only a single configuration (the null configuration) can appear when . More complicated single configurations are sometimes generated, represented by minimal DFA consisting of a single cycle. In most cases (such as rule 76), however, 
contains an infinite number of configurations. However, it appears that even in these cases, all configurations occur on finite cycles: each configuration is invariant under the cellular automaton mapping, or some finite iteration of it. (A result given in Sect. 5 then shows that the must form finite complement languages in these cases.) This implies that changes in the initial state for such cellular automata propagate a distance of at most 
sites. A small initial change can thus ultimately affect a region no larger than 
sites. Such cellular automata must therefore exhibit class 1 or 2 behaviour [2].
For a second set of cellular automata, the form of the minimal DFA does not become fixed after a few time steps, but exhibits a simple growth with time, maintaining a fixed overall structure. The 
for such cellular automata typically increases linearly with time, and increases as some polynomial function of (linear or quadratic for legal , rules). Rule 128 gives an example of this behaviour. Under this rule 
, but all other neighbourhoods map to 
. Any initial sequence of ones thus decreases steadily in length by one site on each side at each time step. After time steps, any pair of ones must be separated by at least 
zeroes; all blocks of the form 
for 
are thus excluded. The first few languages in the sequence generated by successive time steps in the evolution of rule 128 are shown in Fig. 4.1. The minimal DFA are seen to maintain the same overall structure, but include a linearly increasing number of nodes at each time step. The characteristic polynomials corresponding to these DFA are given by
yielding a set entropy which tends to zero at large times, roughly as 
. Rule 160 provides another example in which the minimal DFA maintains the same overall structure, but increases in size with time. In this case, sequences of the form 
for all 
, are excluded after time steps, and the size of the corresponding minimal DFA grows quadratically with time.
Many cellular automata generate sets whose corresponding minimal DFA become much more complicated at each successive time step, and appear to exhibit no simple overall structure.
Figure 4.2 shows the minimal DFA obtained after one and two time steps in the evolution of rule 126. No simple progression in the form of these minimal DFA is seen. 
is a finite complement language, with only the block 
excluded, yielding a characteristic polynomial
giving 
. After two time steps, an infinite sequence of distinct blocks is excluded, starting with the length 12 block 011101101110. The corresponding characteristic polynomial is
with 
. The minimal DFA for 
has 107 states, and the shortest newly-excluded block is 1011100011101 (length 13). increases rapidly with time. After four time steps, the shortest newly-excluded blocks are 10111000011101, 10111000001110 and its reversal (length 14), and 
.
Figures 2.5 and 4.3 give the minimal DFA obtained after one and two time steps in the evolution of rule 18. A considerable increase in complication with time is again evident. After one time step, the shortest of an infinite number of distinct excluded blocks is 1101011 (length 7); after two time steps, the shortest newly-excluded block is 10011011001 (length 11); after three time steps, it is 110010010011 (length 12), and after four time steps it is 1001000010011 (length 13). In this case, as for rule 126, is found to increase monotonically over the range of times investigated. Progressively larger neighbourhoods of the start state are therefore left unchanged in the corresponding minimal DFA. However, as discussed in Sect. 3, need not increase with time, but must in general only satisfy the inequality (3.13). Rule 22 provides an example in which decreases with time. The minimal DFA for in this case is shown in Fig. 4.4; the shortest excluded blocks are 10101001 and 10010101 (length 8). After two time steps, the blocks 1110101 and 1010111 (length 7) are also excluded. The shortest newly-excluded blocks after three time steps are 01000010101, 01000110101, 10000010101 and their reversals (length 11). After four time steps, the shortest newly-excluded blocks are 010110011 and 110011010 (length 9), realizing the equality in (3.13).
generated in the first few time steps of evolution according to cellular automaton rule 128. The DFA maintain the same structure, but increase in size with time. They correspond to finite complement languages, with all blocks of the form excluded for 
.
Rule 126 provides an example in which the set generated after one time step is a finite complement language, but the sets generated at subsequent times are not. Rule 72 exhibits the opposite behaviour (11) ,as shown in Fig. 4.5. After one time step, it yields a set in which the infinite sequence of distinct blocks 111, 1101011, 11001011, 
are excluded (as in for rule 18). After two time steps, however, the block 010 is also excluded. The exclusion of this single block implies exclusion of the infinite set of blocks excluded from . The resulting set thus corresponds to a finite complement language. In general, it can be shown that if a cellular automaton evolves to a finite complement language limit set, then it must do so in a finite number of time steps [34].
The sets generated by most cellular automata never appear to become simpler with time. One exception is rule 72, in which the number of arcs in the minimal DFA for 
is less than in that for . In most cases, the regular language complexity appears to be non-decreasing with time. In fact, whenever the set of configurations generated continues to contract with time, a different regular language must be obtained at each time step. Since there are a limited number of regular languages with complexities below any given value (certainly less than 
), the complexity must on average increase at least slowly with time in this case.
is shown in Fig. 2.5. Rapidly-increasing complexity is again evident. The DFA illustrated here has 47 states.Table 3.1 suggests that a definite set of cellular automata (including rules 18, 22 and 126) yield regular language complexities that grow on average more rapidly than any polynomial in time (perhaps exponentially with time). Many of the cellular automata in this set generically exhibit class 3, chaotic, behaviour, suggesting that rapidly-increasing are a signal for class 3 behaviour in cellular automata.
obtained after one time step in the evolution of the class 3 cellular automaton rule 22. The DFA has all 15 possible states. The shortest excluded block in has length 8, and corresponds to the shortest path from the encircled start state to the one ``incomplete'' node in the DFA graph.In a few cases, such as rule 94, increases rapidly with time, but almost all initial configurations are found to give ultimately periodic behaviour. Nevertheless, special initial conditions (in this case, those in which successive pairs of sites have equal values) can yield chaotic behaviour. Since the set includes all configurations that ever occur, it includes those that give chaotic behaviour, even though they occur with vanishingly small probability. Presumably these configurations would not affect a probabilistic grammar for the set that included only nonzero probability configurations. But the for the grammars discussed here appear to increase rapidly with time whenever any set of configurations in the cellular automaton yield class 3 behaviour.
Some exceptional cases are surjective class 3 cellular automata, such as the additive rules 90 and 150, in which every possible configuration can be generated at any time. The complexity of these and other cellular automata could perhaps be measured by constructing a grammar for the set of possible space-time patterns generated in their evolution. Such a grammar could presumably be characterized in terms of computers with memories arranged in a two-dimensional lattice (cf. [35]) (12).
generated in the first two time steps of evolution under rule 72. is an infinite complement regular language, with the infinite sequence of distinct blocks 111, 1101011, 11001011, excluded. is a finite complement language, with only the blocks 010 and 111 excluded.The local rules 
for the 32 legal , cellular automata of Tables 3.1--3.3 are all distinct. Yet in many cases sets of configurations with the same structure or properties are found to be generated. In some cases, there may exist bijective mappings which transform configurations evolving according to one cellular automaton rule into configurations evolving according to another rule. Several properties of the sets are invariant under such mappings. One example is the set of non-zero roots of the characteristic polynomials . While after one time step several of the cellular automata in Tables 3.1--3.3 yield the same sets of configurations , there are few examples of complete equivalence between pairs of cellular automaton rules. One simple example is rules 146 and 182, which are related by interchange of the roles of 0 and 1.
