|
Articles Cellular Automata Twenty Problems in the Theory of Cellular Automata (1985)
Twenty Problems in the Theory of Cellular Automata (1985) |
|
Many of the complicated systems in nature have been found to have quite simple components. Their complex overall behaviour seems to arise from the cooperative effect of a very large number of parts that each follow rather simple rules. Cellular automata are a class of mathematical models that seem to capture the essential features of this phenomenon. From their study one may hope to abstract some general laws that could extend the laws of thermodynamics to encompass complex and self-organizing systems.
There has been recent progress in analysing some aspects of cellular automata. But many important problems remain. This paper discusses some of the ones that have so far been identified. The problems are intended to be broad in scope, and are probably not easy to solve. To solve any one of them completely will probably require a multitude of subsidiary questions to be asked and answered. But when they are solved, substantial progress towards a theory of cellular automata and perhaps of complex systems in general should have been made.
The emphasis of the paper is on what is not known: for expositions of what is already known about cellular automata, see [1--4]. The paper concentrates on theoretical aspects of cellular automata. There is little discussion of models for actual natural systems. But many of the theoretical issues discussed should have direct consequences for such models.
Cellular automata consist of a homogeneous lattice of sites, with each site taking on one of 
possible values. The sites are updated according to a definite rule that involves a neighbourhood of sites around each one. So in a one-dimensional cellular automaton the value 
of a site at position 
evolves according to
The local rule 
has a range of 
sites. Its form determines the behaviour of the cellular automaton. Some examples of patterns generated by cellular automata are shown in Figs. 1 and 2. Figure 1 shows examples of the four basic classes of behaviour seen in the evolution of cellular automata from disordered initial states. Figure 2 shows patterns generated by evolution from initial configurations containing a single nonzero site.
Cellular automata may be considered as discrete dynamical systems. Their global properties are studied by considering evolution from the set of all possible initial configurations (e.g., [5]). Since most cellular automata are irreversible, the set of configurations that is generated typically contracts with time. Its limiting form at large times determines the asymptotic behaviour of the cellular automaton, and is dominated by the attractors for the evolution. Some of the properties of cellular automata may be characterized in terms of quantities such as entropies and Lyapunov exponents that are used in studies of continuous dynamical systems (e.g., [6]).
); value 0 is shown blank, 1 is grey, and 2 is black. The value of each site at each time step is given by rules that depend on the sum of its own and its nearest neighbours' old values (
totalistic). The cases shown have rules specified by code numbers [5] 1302, 1005, 444 and 792, respectively. 
, totalistic rules with code numbers 1443, 312, 1554, 1617, 1410 and 600, respectively. An alternative view of cellular automata is as information-processing systems [7]. Cellular automaton evolution may be considered to carry out a computation on data represented by the initial sequence of site values. The nature of the evolution may then be characterized using methods from the theory of computation (e.g., [8]). So for example the sets of configurations generated in the evolution may be described as formal languages: a one-dimensional cellular automaton gives a regular formal language after any finite number of time steps [7]. One suspects that in many cases the computations corresponding to cellular automaton evolution are sufficiently complicated as to be irreducible (cf. [9]). In that case, there can be essentially no short-cut to determining the outcome of the cellular automaton evolution by explicit simulation or observation of each step. This implies that certain limiting properties of the cellular automaton are undecidable, since to find them would require an infinite computation.
The problems discussed here address both dynamical systems theory and computation theory aspects of cellular automata. But probably the most valuable insights will come from the interplay between these two aspects.
