Problem 14

What are the connections between the computational and statistical characteristics of cellular automata?

The rate of information transmission is one attribute of cellular automata that potentially affects both computational and statistical properties. On the statistical side, the rate of information transmission gives the Lyapunov exponent for the cellular automaton evolution. Class 1 and 2 cellular automata have zero Lyapunov exponents, so that information almost always remains localized, and the value of a particular site at any time can almost always be determined from the initial values of a bounded neighbourhood of initial sites. As a consequence, the limit sets for one-dimensional such cellular automata correspond to regular languages. The configurations can thus be generated by an essentially Markovian process, in which there are no long-range correlations between different parts.

Class 3 and 4 cellular automata have positive Lyapunov exponents, so that a small initial change expands with time. The value of a particular site after many time steps thus depends in general on an ever-increasing region in the initial state. The limit sets for such cellular automata can thus involve long-range correlations, and need not correspond to regular languages. If class 4 cellular automata are generically capable of universal computation, then their limit sets should be unrestricted, in general non-recursive, formal languages. Some arguments can be given that class 3 cellular automata should yield limit sets that correspond to context-sensitive languages. In general, one suspects that dynamical systems that exhibit chaotic behaviour characterized by positive Lyapunov exponents should yield limit sets that are more complicated than regular languages.

When the limit set for a cellular automaton is a regular language, its spatial entropy can be computed, and is given by the logarithm of an algebraic integer. If the limit set is a context-free language, then it seems that the entropy is always the logarithm of some algebraic number. But for context-sensitive and more complicated languages, the entropy is in general non-computable. It may thus be common to find class 3 and 4 cellular automata for which the entropy of their limit sets is non-computable.

The computational structure of sets generated in the evolution of two and higher dimensional cellular automata can be very complicated even after a finite number of time steps. In particular, while in one-dimensional cellular automata the set of configurations that can be generated at any finite time forms a regular formal language, this set can be non-recursive in two-dimensional cellular automata [12, 42]. The essential origin of this difference is that there is an iterative procedure to find the possible predecessors of arbitrarily long sequences in one-dimensional cellular automata, but no such procedure exists for two-dimensional cellular automata. In fact, even the problem of finding configurations that evolve periodically in time in a two-dimensional cellular automaton appears to be equivalent to the domino tiling problem, which is known to be formally undecidable [43]. Nevertheless, it seems likely that only two-dimensional cellular automata in which information transmission can occur throughout the plane, as revealed by positive Lyapunov exponents in all directions, exhibit such complications, and give non-recursive sets at finite times.

The grammar for a formal language specifies which sequences occur in the language, but not how often they occur. It does not for example distinguish sequences that occur with zero probability from those that occur with positive probability. However, it is the probable, rather than the possible, behaviour of cellular automata that is most significant in determining their statistical properties, such as Lyapunov exponents and measure entropies. There are class 1 and 2 cellular automata in which a set of states of measure zero yields class 3 behaviour: this is irrelevant in the Lyapunov exponent or the measure entropy, but affects the topological entropy, and the structure of the grammar for the limit set. One should construct formal languages that include probabilities for configurations. A suitable approach may be to consider stochastic automata, closely related to standard Markov chains.

previous  l  next