1. Introduction

Cellular automata are mathematical models for complex natural systems containing large numbers of simple identical components with local interactions. They consist of a lattice of sites, each with a finite set of possible values. The values of the sites evolve synchronously in discrete time steps according to identical rules. The value of a particular site is determined by the previous values of a neighbourhood of sites around it.

The behaviour of a simple set of cellular automata was discussed in ref. 1, where extensive references were given. It was shown that despite their simple construction, some cellular automata are capable of complex behaviour. This paper discusses the nature of this complex behaviour, its characterization, and classification. Based on investigation of a large sample of cellular automata, it suggests that many (perhaps all) cellular automata fall into four basic behaviour classes. Cellular automata within each class exhibit qualitatively similar behaviour. The small number of classes implies considerable universality in the qualitative behaviour of cellular automata. This universality implies that many details of the construction of a cellular automaton are irrelevant in determining its qualitative behaviour. Thus complex physical and biological systems may lie in the same universality classes as the idealized mathematical models provided by cellular automata. Knowledge of cellular automaton behaviour may then yield rather general results on the behaviour of complex natural systems.

Cellular automata may be considered as discrete dynamical systems. In almost all cases, cellular automaton evolution is irreversible. Trajectories in the configuration space for cellular automata therefore merge with time, and after many time steps, trajectories starting from almost all initial states become concentrated onto ``attractors''. These attractors typically contain only a very small fraction of possible states. Evolution to attractors from arbitrary initial states allows for ``self-organizing'' behaviour, in which structure may evolve at large times from structureless initial states. The nature of the attractors determines the form and extent of such structures.

The four classes mentioned above characterize the attractors in cellular automaton evolution. The attractors in classes 1, 2 and 3 are roughly analogous respectively to the limit points, limit cycles and chaotic (``strange'') attractors found in continuous dynamical systems. Cellular automata of the fourth class behave in a more complicated manner, and are conjectured to be capable of universal computation, so that their evolution may implement any finite algorithm.

The different classes of cellular automaton behaviour allow different levels of prediction of the outcome of cellular automaton evolution from particular initial states. In the first class, the outcome of the evolution is determined (with probability 1), independent of the initial state. In the second class, the value of a particular site at large times is determined by the initial values of sites in a limited region. In the third class, a particular site value depends on the values of an ever-increasing number of initial sites. Random initial values then lead to chaotic behaviour. Nevertheless, given the necessary set of initial values, it is conjectured that the value of a site in a class 3 cellular automaton may be determined by a simple algorithm. On the other hand, in class 4 cellular automata, a particular site value may depend on many initial site values, and may apparently be determined only by an algorithm equivalent in complexity to explicit simulation of the cellular automaton evolution. For these cellular automata, no effective prediction is possible; their behaviour may be determined only by explicit simulation.

This paper describes some preliminary steps towards a general theory of cellular automaton behaviour. Section 2 below introduces notation and formalism for cellular automata. Section 3 discusses general qualitative features of cellular automaton evolution illustrating the four behaviour classes mentioned above. Section 4 introduces entropies and dimensions which characterize global features of cellular automaton evolution. Successive sections consider each of the four classes of cellular automata in turn. The last section discusses some tentative conclusions.

This paper covers a broad area, and includes many conjectures and tentative results. It is not intended as a rigorous mathematical treatment.

previous  l  next