ABSTRACT: The elements of the computational mechanics of one-dimensional cellular automata (CA) are developed and applied to a number of specific examples.
Regular domains are introduced as the pattern bases of a wide class of CA. Pattern bases are the fundamental patterns emerging during a system's evolution, governing and organizing its behavior, and determining the form of its analysis. Coherent structures---walls, dislocations and generally "particles"---are defined as points at which the domain pattern breaks down. A method is given for constructing transducer machines that perform nonlinear spatial filtering such that the resulting space-time patterns reveal the domains and the intervening walls and dislocations. A number of important pattern quantifiers are defined. These include entropy and complexity densities, single-site statistics, difference patterns and difference plumes, and domain interface patterns and plumes.
Domains, regular vicinities and regular attractors are introduced as basic elements in the qualitative pattern dynamics of CA. This draws a connection between the qualitative theory of dynamical systems and the evolution of patterns, as described by the domains and domain walls. The qualitative pattern dynamics of a CA is summarized by an attractor-basin portrait giving its regular attractors, their basins, and the basins' separatrices.
A range of examples serve to illustrate utility and validity of the definitions and methods developed. Domains in a variety of elementary CA are identified, and transducers for filtering the domains are constructed and applied to space-time data. The statistical and computational properties of dislocation trajectories in a particular CA are discussed. A cellular automaton having multiple coexisting chaotic domains of different complexities and entropies is investigated. The attractor-basin portrait of nonlinear, chaotic elementary CA rule 18 is given. The CA's basins are analyzed in terms of subbasin and portal structures associated with particle annihilation. A detailed study is made of the attractors' convergence properties, both their temporal behavior and their dependence on system size.