9. Discussion

Cellular automata are simple in construction, but are capable of very complex behaviour. This paper has suggested that a considerable universality exists in this complex behaviour. Evidence has been presented that all one-dimensional cellular automata fall into only four basic classes. In the first class, evolution from almost all initial states leads ultimately to a unique homogeneous state. The second class evolves to simple separated structures. Evolution of the third class of cellular automata leads to chaotic patterns, with varying degrees of structure. The behaviours of these three classes of cellular automata are analogous to the limit points, limit cycles and chaotic (``strange'') attractors found in continuous dynamical systems. The fourth class of cellular automata exhibits still more complicated behaviour, and its members are conjectured to be capable of universal computation.

Even starting from disordered or random initial configurations, cellular automata evolve to generate characteristic patterns. Such self-organizing behaviour occurs by virtue of the irreversibility of cellular automaton evolution. Starting from almost any initial state, the evolution leads to attractors containing a small subset of all possible states. At least for the first three classes of cellular automata, the states in these attractors form a Cantor set, with characteristic fractal and other dimensions. For the first and second classes, the states in the attractor may be specified as sentences with a regular grammar. For the fourth class, the attractors may be arbitrarily complicated, and no simple statistical characterizations appear possible.

The four classes of cellular automata may be distinguished by the level of predictability of their ``final'' large time behaviour given their initial state. For the first class, all initial states yield the same final state, and complete prediction is trivial. In the second class, each region of the final state depends only on a finite region of the initial state; knowledge of a small region in the initial state thus suffices to predict the form of a region in the final state. In the evolution of the third class of cellular automata, the effects of changes in the initial state almost always propagate forever at a finite speed. A particular region thus depends on a region of the initial state of ever-increasing size. Hence any prediction of the ``final'' state requires complete knowledge of the initial state. Finally, in the fourth class of cellular automata, regions of the final state again depend on arbitrarily large regions of the initial state. However, if cellular automata in the class are indeed capable of universal computation, then this dependence may be arbitrarily complex, and the behaviour of the system can be found by no procedure significantly simpler than direct simulation. No meaningful prediction is therefore possible for such systems.

previous  l  next