|
Articles Mathematics Algebraic Properties of Cellular Automata (1984)
Algebraic Properties of Cellular Automata (1984) |
|
Equation (2.3) defines the time evolution for a special class of ``additive'' cellular automata, in which the value of a site is given by a linear combination (in 
) of the values of its neighbours on the previous time step. In this section we discuss ``non-additive'' cellular automata, which evolve according to
where 
is an arbitrary function over , not reducible to linear form. The absence of additivity in general prevents use of the algebraic techniques developed for additive cellular automata in Sects. 3 and 4. The difficulties in the analysis of non-additive cellular automata are analogous to those encountered in the analysis of non-linear feedback shift registers (cf. [11]). In fact, the possibility of universal computation with sufficiently complex non-additive cellular automata demonstrates that a complete analysis of these systems is fundamentally impossible. Some results are nevertheless available (cf. [12]). This section illustrates some methods which may be applied to the analysis of non-additive cellular automata, and some of the results which may be obtained.
As in [1], most of the discussion in this section will be for the case 
. In this case, there are 32 possible functions 
satisfying the symmetry condition
and the quiescence condition
Reference [1] showed the existence of two classes of these ``legal'' cellular automata. The ``simple'' class evolved to fixed points or short cycles after a small number of time steps. The ``complex'' class (which included the additive rules discussed above) exhibited more complicated behaviour.
We consider as an example the complex non-additive rule defined by
and referred to as rule 18 in [1]. This function yields a time evolution rule equivalent to
The rule does not in general satisfy any superposition principle. However, for the special class of configurations with 
or 
, Eq. (5.3) implies that the evolution of even (odd) sites on even (odd) time steps is given simply by the rule defined in Sect. 3A. Any configuration may be considered as a sequence of ``domains'' in which all even (or odd) sites have value zero, separated by ``domain walls'' or ``kinks'' [13]. In the course of time the kinks annihilate in pairs. If sites are nonzero only in some finite region, then at sufficiently large times in an infinite cellular automaton, all kinks (except perhaps one) will have annihilated, and an effectively additive system will result. However, out of all 
possible initial configurations for a cellular automaton with 
sites and periodic boundary conditions, only a small fraction are found to evolve to this form before a cycle is reached: in most cases, ``kinks'' are frozen into cycles, and contribute to global behaviour in an essential fashion.
Typical examples of the state transition diagrams obtained with the rule (5.3) are shown in Fig. 5. They are seen to be much less regular than those for additive rules illustrated in Fig. 2. In particular, not all transient trees are identical, and few of the trees are balanced. Just as for the additive rules discussed in Sects. 3 and 4, only a fraction of the possible configurations may be reached by evolution according to Eq. (5.3); the rest are unreachable and appear as nodes with zero in-degree on the periphery of the state transition diagram of Fig. 5. An explicit characterization of these unreachable configurations may be found by lengthy but straightforward analysis.
A configuration is unreachable by cellular automaton time evolution according to Eq. (5.3) if and only if one of the following conditions holds:
appears, with an odd number of the 
having value 1. The two 11 sequences may be cyclically identified.
The number of reachable configurations may now be found by enumerating the configurations defined by Lemma 5.1. This problem is analogous to the enumeration of legal sentences in a formal language. As a simple example of the techniques required (e.g. [14]), consider the enumeration of strings of symbols 
or 
in which no sequence 111 appears (no periodicity is assumed). Let the number of such strings be 
. In addition, let 
be the number of length strings containing no 111 sequences in their first 
positions, but terminating with the sequence 111. Then
and
The recurrence relations (5.4) may be solved by a generating function technique. With
Eq. (5.4) may be written as
Solving these equations yields the result
Results for specific are obtained as the coefficients of 
in a series expansion of 
. Taking
Eq. (5.5a) may be inverted to yield
where the 
are the roots of 
(all assumed distinct), and prime denotes differentiation. This yields finally
The behaviour of the coefficients for large is dominated by the first term, associated with the smallest root of 
. The first ten values of 
are 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504.
A lengthy calculation shows that the number of possible strings of length which do not satisfy the conditions in Lemma 5.1, and may therefore be reached by evolution of the cellular automaton defined by Eq. (5.3), is given as the coefficient of in the expansion of the generating function
Inverting according to Eq. (5.5c), the number of reachable configurations of length is given by
where 
is the real root of 
, 
, and 
, 
. The first ten values of 
are 1, 1, 4, 7, 11, 19, 36, 67, 121, 216. For large , 
. Equation (5.8) shows that corrections decrease rapidly and smoothly with . This behaviour is to be contrasted with the irregular behaviour as a function of found for additive cellular automata in Theorems 3.1 and 4.2.
Equation (5.8) shows that the fraction of all possible configurations which are reachable after one time step in the evolution of the cellular automaton of Eq. (5.2) is approximately 
. Thus, starting from an initial maximal entropy ensemble with 
, evolution for one time step according to Eq. (5.2) yields a set entropy
The irregularity of the transient trees illustrated in Fig. 5 implies a measure entropy 
.
The result (5.9) becomes exact in the limit 
. A direct derivation in this limit is given in [17], [18], where it is also shown that the set of infinite configurations generated forms a regular formal language. The set continues to contract with time, so that the set entropy decreases below the value given by Eq. (5.9) [18].
Techniques similar to those used in the derivation of Eq. (5.5) may in principle be used to deduce the number of configurations reached after any given number of steps in the evolution of the cellular automaton (5.2). The fraction of configurations which appear in cycles is an irregular function of ; some results for small are given in Table 3.
