Problem 4

What statistical quantities characterize cellular automaton behaviour?

There are several direct statistical measurements that can be made on cellular automaton configurations. Very simple examples are densities of sites or blocks of sites with particular values. Such densities are closely related to block entropies; their limit for large block sizes is the spatial entropy of the cellular automaton configurations, equal to the dimension of the Cantor set formed by the configurations (e.g., [5]). Another direct statistical measurement that can be made is of correlation functions, which describe the interdependence of the values of separated sites [2]. For class 1 and 2 cellular automata, one expects that the correlation functions vanish beyond some critical distance. For class 3 cellular automata there are indications that the correlation functions typically fall off exponentially with distance. For class 4 cellular automata, the large distance part of the correlation function is dominated by propagating persistent structures, and may decrease slowly.

Power spectra or Fourier transforms provide other statistical measures of cellular automaton configurations. (Entirely discrete Walsh-Hadamard transforms [14] may be slightly more suitable.) Their form is not yet known. But many processes in cellular automata occur on a variety of spatial or temporal scales, so one expects definite structure in their transforms.

Beyond entropies and Lyapunov exponents, dynamical systems theory suggests that zeta functions may give a characterization of the global behaviour of cellular automata. Zeta functions measure the density of periodic sequences in cellular automaton configurations, and may possibly be related to Fourier transforms. The fact that the set of configurations generated from all possible initial states at a particular time step in the evolution of a cellular automaton forms a regular language (or ``sofic system'') implies that the corresponding zeta function is rational [15].

previous  l  next