Problem 15

How random are the sequences generated by cellular automata?

The spatial sequences obtained after a finite number of steps in the evolution of a one-dimensional cellular automaton starting from all possible initial states are known to form a regular formal language. But no such characterization is known for the temporal sequences generated by cellular automata. At least for cellular automata capable of universal computation, these sequences can be non-recursive. But the generic behaviour is not known, and no non-trivial examples have yet been given.

One question is to what extent the initial state of a cellular automaton can be reconstructed from a knowledge of the time series of values of a few sites. An essentially equivalent question is how wide a patch of sites need to be considered to compute the invariant entropy of the cellular automaton mapping. When the mapping is surjective and expansive (so that roughly information transmission occurs at a positive rate), only a finite width is required (e.g., [44]). Nevertheless, the transformation necessary to find the initial state from the temporal sequence may be very complicated. In particular, there may be effectively no better method than to try all exponentially many possible initial states. Temporal sequences in cellular automata are thus candidates for use in pseudorandom number generation and in cryptography [20].

The patterns generated by some cellular automata evolving from initial states consisting of simple seeds have a simple form. They may be asymptotically homogeneous, or may correspond to regular fractals. But many cellular automata yield complicated patterns even starting from an initial state as simple as a single nonzero site. Some examples are shown in Fig. 2. It is remarkable that such complicated and intricate patterns can be generated in such a simple system.

Often the temporal sequences that appear in these patterns have a seemingly random form, and satisfy many statistical tests for randomness. There is empirical evidence that in many cases the sequence of values taken on say by the centre site in the pattern contains all possible subsequences with equal frequencies, so that the whole sequence effectively has maximal measure entropy. A simple example of this phenomenon occurs in the , rule number 30 ().

Systems that exhibit chaotic behaviour usually start from initial conditions that contain an infinite amount of information, either in the form of an infinite sequence of cellular automaton site values, or the infinite sequence of digits in a real number. Their irregular behaviour with time can then be viewed as a progressive excavation of the initial conditions. The chaotic behaviour seen in Fig. 2 is however of another kind: it occurs as a consequence of the dynamics of the system, even though the initial conditions are simple. It may well be that this kind of chaos is central to physical phenomena such as fluid turbulence.

It is important to investigate the mathematical bases for such behaviour. The closest analogies seem to lie in number theory. The integers generated for example by repeated application of a linear congruence transformation form a pseudorandom sequence (e.g., [45]), often used in practical applications. The linearity of this system makes it amenable to a rather complete number theoretical analysis, which provides formulae for computing the th integer in the sequence directly from the original seed, with working out all the intermediates. It seems likely that such analyses, and the resulting short cuts, are not possible in most nonlinear cellular automata. The randomness produced in these systems may be more like the randomness say of the digits of . In some cases it is in fact possible to cast essentially number theoretical problems in terms of questions about patterns generated by cellular automata. One example concerns the sequence of leading binary digits in the fractional parts of successive powers of [46]. There is empirical evidence that all possible blocks of digits occur in this sequence, so that in a sense it has maximal entropy. The sequence corresponds to the time series of values of the central site in the pattern generated by a particular cellular automaton from a simple initial state.

previous  l  next