Complexity Measures and Cellular Automata
Kristian Lindgren
Physical Resource Theory Group, Chalmers University of Technology,
S-412 96 Göteborg, Sweden
Mats G. Nordahl
Institute of Theoretical Physics, S-412 96 Göteborg, Sweden
Abstract
Various observables measuring the complexity of an ensemble of patterns are discussed, in particular statistical quantities related to the convergence of block entropies, and computation theoretical quantitites related to a grammatical description of the ensemble. These measures of complexity are applied to one-dimensional cellular automata, by characterizing the time evolution of the probability measure on configuration space in terms of stochastic finite automata. In particular it is found that the effective measure complexity increases linearly in time for an additive rule with a random initial state with density 
. Some results on the convergence of block entropies for regular languages are shown, and context-free languages are also discussed. These results are used in an attempt to interpret the critical exponents observed by Grassberger in the convergence of block entropies for certain chaotic cellular automaton rules.
