7. Discussion

This paper has taken some preliminary steps in the application of computation theory to the global analysis of cellular automata. Cellular automata are viewed as computers, whose time evolution processes the information specified by their initial configurations. Many aspects of this information processing may be described in terms of computation theory. The intrinsic discreteness of cellular automata allows for immediate identifications with conventional computational systems; but the basic approach and many of the results obtained should be applicable to many other dynamical systems.

Self-organization in cellular automata involves the generation of distinguished sets of configurations with time. These sets are described as formal languages in computation theory terms. Each configuration corresponds to a word in a language, and is formed from a sequence of symbols according to definite grammatical rules. These grammatical rules provide a complete and succinct specification of the sets generated by the cellular automaton evolution.

Section 2 showed that, starting with all possible initial configurations, the sets generated by a finite number of time steps of cellular automaton evolution always correspond to regular formal languages. Such languages are recognized by finite automata. These finite automata are specified by finite state transition graphs; words in the languages correspond to all possible paths through these graphs. The (limiting) set entropies of such regular languages are then given as logarithms of the algebraic integers corresponding to the largest eigenvalues of the incidence matrices for their state transition graphs.

In general, several different finite automata or regular grammars may yield the same regular language. However, it is always possible to find a simplest finite automaton, or set of grammatical rules, which correspond to any particular regular language. This simplest finite automaton provides a canonical representation for sets generated by cellular automaton evolution, and its size (number of states) gives a measure of their ``complexity.'' The larger the ``regular language complexity'' for a set of configurations, the more complicated is the minimal set of grammatical rules necessary to describe it as a regular language.

Section 4 suggests the general result that the regular language complexity is non-decreasing with time for all cellular automata. This result gives a quantitative characterization of progressive self-organization in cellular automata. It may give a first indication of a generalization of the second law of thermodynamics to irreversible systems.

Entropy may be estimated from experimental data by fitting parameters in simple models which reproduce the data. Extraction of regular language complexities from experimental data requires the identification of maximal (regular language) patterns in the data, or the construction of a minimal (finite automaton) model that generates the data. Given perfect data (and an upper bound on the regular language complexity), a direct method may be used (e.g. [48]). In practice, it will probably be convenient to construct stochastic finite automata which provide probabilistic reproductions of the available data (cf. estimates for the structure of Markovian sources (e.g. [49])).

Dynamical systems theory methods were used in [2] to identify four general classes of cellular automaton behaviour. Sections 4 and 6 suggested computation theory characterizations of these classes. The limit sets for cellular automata with only class 1 or 2 behaviour are regular languages. For most class 3 and 4 cellular automata, the regular language complexity increases steadily with time, so that the set of configurations obtained in the large time limit does not usually form a regular language. Instead (at least for appropriate finite size configurations) the limit sets for class 3 cellular automata appear to correspond to context-sensitive languages, while those for class 4 cellular automata correspond to general languages.

Regular languages are sufficiently simple that their properties may be determined by finite computational procedures. Properties of context-free and more complicated languages are, however, often not computable by finite means. Thus, for example, the minimal grammars for such languages (whose sizes would provide analogues of the regular language complexity) cannot in general be found by finite computations. Moreover, for context-sensitive and general languages, even quantities such as entropy are formally non-computable.

When cellular automaton evolution is viewed as computation, one may consider that the limiting properties of a cellular automaton are determined by an infinite computational process. One should not expect in general that the results of this infinite process can be summarized in finite mathematical terms. For sufficiently simple cellular automata, apparently those of classes 1 and 2, however, it is nevertheless possible to ``short cut'' the infinite processes of cellular automaton evolution, and to give a finite specification of their limiting properties. For most class 3 and 4 cellular automata, no such short cut appears possible: their behaviour may in general be determined by no procedure significantly faster than explicit simulation, and many of their limiting properties cannot be determined by any finite computational process. (Such non-computable limiting behaviour would be an immediate consequence of the universal computation capability conjectured for class 4 cellular automata, but does not depend on it.)

Non-computability and undecidability are common phenomena in the systems investigated in pure mathematics, logic and computation. But they have not been identified in the systems considered in theoretical physics. In many physical theories one can in fact imagine constructing complicated systems which behave, for example, as universal computers, and for which undecidable propositions may be formulated. Cellular automata (and other dynamical systems) may be considered as simple physical theories. This paper has suggested that in fact even simple, natural, questions concerning the limiting behaviour of cellular automata are often undecidable (except for very simple systems such as those corresponding to class 1 and 2 cellular automata). One may speculate that undecidability is common in all but the most trivial physical theories. Even simply-formulated problems in theoretical physics may be found to be provably insoluble.

Undecidability and non-computability are features of problems which attempt to summarize the consequences of infinite processes. Finite processes may always be carried out explicitly. For some particularly simple processes, the consequences of a large, but finite, number of steps may be deduced by a procedure involving only a small number of steps. But at least for many computational processes (e.g. [28]), it is believed that no such short cut exists: each step (or each possibility) must in fact be carried out explicitly. It was suggested that this phenomenon is common in cellular automata. One may speculate that it is widespread in physical systems. No simple theory or formula could ever be given for the overall behaviour of such systems: the consequences of their evolution could not be predicted, but could effectively be found only by direct simulation or observation.

previous  l  next