6. Discussion

The analysis of additive cellular automata in Sects. 3 and 4 yielded results on the global behaviour of additive cellular automata more complete than those available for most other dynamical systems. The extensive analysis was made possible by the discrete nature of cellular automata, and by the additivity property which led to the algebraic approach developed in Sect. 3. Similar algebraic techniques should be applicable to some other discrete dynamical systems.

The analysis of global properties of cellular automata made in this paper complements the analysis of local properties of ref. [1].

One feature of the results on additive cellular automata found in Sects. 3 and 4, is the dependence of global quantities not only on the magnitude of the size parameter , but also on its number theoretical properties. This behaviour is shared by many dynamical systems, both discrete and continuous. It leads to the irregular variation of quantities such as cycle lengths with , illustrated in Table 1 and Fig. 3. In physical realizations of cellular automata with large size , an average is presumably performed over a range of values, and irregular dependence on is effectively smoothed out. A similar irregular dependence is found on the number of possible values for each site: simple results are found only when is prime.

Despite such detailed dependence on , results such as Theorems 4.1, 4.2, and 4.3 show that global properties of additive cellular automata exhibit a considerable universality, and independence of detailed aspects of their construction. This property is again shared by many other dynamical systems. It potentially allows for generic results, valid both in the simple cases which may easily be analysed, and in the presumably complicated cases which occur in real physical systems.

The discrete nature of cellular automata makes possible an explicit analysis of their global behaviour in terms of transitions in the discrete phase space of their configurations. The results of Sect. 4 provide a rather complete characterization of the structure of the state transition diagrams for additive cellular automata. The state transition diagrams consist of trees corresponding to irreversible ''transients'', leading to ''attractors'' in the form of distinct finite cycles. The irreversibility of the cellular automata is explicitly manifest in the convergence of several distinct configurations to single configurations through motion towards the roots of the trees. This irreversibility leads to a decrease in the entropy of an initially equiprobable ensemble of cellular automaton configurations; the results of Sect. 4 show that in most cases the entropy decreases by a fixed amount at each time step, reflecting the balanced nature of the trees. Theorem 4.3 gives an algebraic characterization of the magnitude of the irreversibility, in terms of the in-degrees of nodes in the trees. The length of the transients during which the entropy decreases is given by the height of the trees in Theorem 4.3, and is found always to be less than . After these transients, any initial configurations evolve to configurations on attractors or cycles. Theorem 4.3 gives the total number of configurations on cycles in terms of and algebraic properties of the cellular automaton time evolution polynomial. At one extreme, all configurations may be on cycles, while at the other extreme, all initial configurations may evolve to a single limit point consisting simply of the null configuration.

Theorem 4.1 gives a rather general result on the lengths of cycles in additive cellular automata. The maximum possible cycle length is found to be of order the square root of the total number of possible configurations. Rather long cycles are therefore possible. No simple results on the total number of distinct cycles or attractors were found; however, empirical results suggest that most cycles have a length equal to the maximal length for a particular cellular automaton.

The global properties of additive cellular automata may be compared with those of other mathematical systems. One closely related class of systems are linear feedback shift registers. Most results in this case concentrate on analogues of the cellular automaton discussed in Sect. 3, but with the values at a particular time step in general depending on those of a few far-distant sites. The boundary conditions assumed for feedback shift registers are typically more complicated than the periodic ones assumed for cellular automata in Sect. 3 and most of Sect. 4. The lack of symmetry in these boundary conditions allows for maximal length shift register sequences, in which all possible configurations occur on a single cycle [2], [3].

A second mathematical system potentially analogous to cellular automata is a random mapping [15]. While the average cycle length for random mappings is comparable to the maximal cycle length for cellular automata, the probability for a node in the state transition diagram of a random mapping to have in-degree is , and is much more sharply peaked at low values than for a cellular automaton, leading to many differences in global properties.

Non-additive cellular automata are not amenable to the algebraic techniques used in Sects. 3 and 4 for the additive case. Section 5 nevertheless discussed some properties of non-additive cellular automata, concentrating on a simple one-dimensional example with two possible values at each site. Figure 5 indicates that the state transition diagrams for such non-additive cellular automata are less regular than those for additive cellular automata. Combinatorial methods were nevertheless used to derive the fraction of configurations with no predecessors in these diagrams, giving the irreversibility and thus entropy decrease associated with one time step in the cellular automaton evolution. Unlike the case of additive cellular automata, the result was found to be a smooth function of .

previous  l  next