Problem 1

What overall classification of cellular automaton behaviour can be given?

Experimental mathematics provides a first approach to this problem. One performs explicit simulations of cellular automata, and tries to find empirical rules for their behaviour. These may then suggest results that can be investigated by more conventional mathematical methods.

An extensive experimental study [5] suggests that the patterns generated in the evolution of cellular automata from disordered initial states can be grouped into four general classes, illustrated in Fig. 1:

1. Evolves to homogeneous state.
2. Evolves to simple separated periodic structures.
3. Yields chaotic aperiodic patterns.
4. Yields complex pattern of localized structures.

The classification is at first qualitative. But there are several ways to make it more quantitative, and to formulate precise definitions for the four classes. For some cellular automaton rules, one expects that all definitions will agree. But there are likely to be borderline cases where definitions will disagree.

Continuous dynamical systems provide analogues for the classes of behaviour seen in cellular automata. Class 1 cellular automata show limit points, while class 2 cellular automata may be considered to evolve to limit cycles. Class 3 cellular automata exhibit chaotic behaviour analogous to that found with strange attractors. Class 4 cellular automata effectively have very long transients, and no direct analogue for them has been identified among continuous dynamical systems.

Dynamical systems theory gives a first approach to the quantitative characterization of cellular automaton behaviour. Various kinds of entropy may be defined for cellular automata. Each counts the number of possible sequences of site values corresponding to some spacetime region. For example, the spatial entropy gives the dimension of the set of configurations that can be generated at some time step in the evolution of the cellular automaton, starting from all possible initial states. There are in general ( is the number of possible values for each site) possible sequences of values for a block of sites in this set of configurations. The spatial topological entropy is given by . One may also define a spatial measure entropy formed from the probabilities of possible sequences. Temporal entropies may then be defined to count the number of sequences that occur in the time series of values taken on by each site. Topological entropies reflect the possible configurations of a system; measure entropies reflect those that are probable, and are insensitive to phenomena that occur with zero probability. A tentative definition of the four classes of cellular automaton behaviour may be given in terms of measure entropies. Class 1 has zero spatial and temporal measure entropy. Class 2 has zero temporal measure entropy, since it almost always yields periodic structures, but has positive spatial measure entropy. Class 3 has positive spatial and temporal measure entropies.

[ Figure 3 ] Patterns of differences generated by changing a single initial site value in the cellular automata of Fig. 1. In the first two cases, the difference (shown modulo three) is seen to remain localized. In the second two cases, it grows progressively with time.

Another property of cellular automata is their stability under small perturbations in initial conditions. Figure 3 shows differences in patterns generated by cellular automata induced by changes in a single initial site value. Such differences almost always die out in class 1 cellular automata. In class 2 cellular automata, they may persist, but remain localized. In class 3 cellular automata, however, they typically expand at an asymptotically constant rate. The rate of this expansion gives the Lyapunov exponent for the evolution [5, 10], and measures the speed of propagation of information about the initial configuration in the cellular automaton. Class 4 cellular automata give rise to a pattern of differences that typically expands irregularly with time.

The four classes of cellular automaton behaviour identified here can be defined to be complete. But there are some cellular automata whose behaviour should probably be considered intermediate between the classes. In particular, there are many where there is a clear superposition of two classes of behaviour. So for example sites with values 0 and 1 can exhibit class 2 behaviour, while sites with values 0 and 2 show class 3 behaviour. The result is a sequence of chaotic regions separated by rigid ``walls''.

Even at a qualitative level, it is possible that definite subclasses of the four classes of cellular automaton behaviour may be identified. Some class 3 cellular automata in one dimension seem to give patterns with large triangular clearings and low but presumably nonzero entropies; others give highly irregular patterns with no long-range structure. No clear statistical difference between these kinds of class 3 cellular automata has yet been found. But it is possible that one exists. Among class 4 cellular automata there seem to be some definite subclasses in which persistent or almost persistent structures of rather particular kinds occur.

previous  l  next