Computational Mechanics of Cellular Automata: An Example

J. E. Hanson
Santa Fe Instutute
1399 Hyde Park Rd.
Santa Fe, NM 87501, USA

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

ABSTRACT: We illustrate and extend the techniques of computational mechanics in explicating the structures that emerge in the space-time behavior of elementary one-dimensional cellular automaton rule 54. The CA's dominant regular domain is identified and a domain filter is constructed to locate and classify defects in the domain. The primary particles are identified and a range of interparticle interactions is studied. The deterministic equation of motion of the filtered space-time behavior is derived. Filters of increasing sophistication are constructed for the efficient gathering of particle statistics and for the identification of higher-level defects, particle interactions, and secondary domains. We define the emergence time at which the space-time behavior condenses into configurations consisting only of domains, particles, and particle interactions. Taken together, these techniques serve as the basis for the investigation of pattern evolution and self-organization in this representative system.


J. E. Hanson and J. P. Crutchfield, "Computational Mechanics of Cellular Automata: An Example", Physica D 103 (1997) 169-189.
Santa Fe Institute Working Paper 95-10-95.
[pdf] = 4220kB
[ps.gz] = 496kB
Pages 1-15: [ps.gz] = 320kB
Page 16: [ps.gz] = 1084kB
Page 17-21: [ps.gz] = 80kB.