Turbulent Pattern Bases for Cellular Automata

J. P. Crutchfield and J. E. Hanson
Physics Department
University of California
Berkeley, California 94720, USA

ABSTRACT: Unpredictable patterns generated by cellular automata (CA) can be decomposed with respect to a turbulent, positive entropy rate pattern basis. The resulting filtered patterns uncover significant structural organization in a CA's dynamics and information processing capabilities. We illustrate the decomposition technique by analyzing a binary, range-2 cellular automaton having two invariant chaotic domains of different complexities and entropies. Once identified, the domains are seen to organize the CA's state space and to dominate its evolution. Starting from the domains' structures, we show how to construct a finite-state transducer that performs nonlinear spatial filtering such that the resulting space-time patterns reveal the domains and the intervening walls and dislocations. To show the statistical consequences of domain detection, we compare the entropy and complexity densities of each domain with the globally averaged quantities. A more graphical comparison uses difference patterns and difference plumes which trace the space-time influence of a single-site perturbation. We also investigate the diversity of walls and particles emanating from the interface between two adjacent domains.


J. P. Crutchfield and J. E. Hanson, "Turbulent Pattern Bases for Cellular Automata", Physica D 69 (1993) 279-301. [ps.gz]= 395kb [pdf]= 1,318kb
Santa Fe Institute Working Paper 93-03-010.

In parts:
Pages 1-12: [ps.gz]= 132kb
Pages 13-24: [ps.gz]= 218kb
Pages 25-32: [ps.gz]= 60kb