Upper Bound on the Products of Particle Interactions in Cellular Automata
Particle-like objects are observed to propagate and interact in many spatially extended dynamical systems. For one of the simplest classes of such systems, one-dimensional cellular automata, we establish a rigorous upper bound on the number of distinct products that these interactions can generate. The upper bound is controlled by the structural complexity of the interacting particles -- a quantity which is defined here and which measures the amount of spatio-temporal information that a particle stores. Along the way we establish a number of properties of domains and particles that follow from the computational mechanics analysis of cellular automata; thereby eludicating why that approach is of general utility. The upper bound is tested against several relatively complex domain-particle cellular automata and found to be tight. PACS: 45.70.Qj, 05.45, 05.65+b
Year of publication: |
2000-09
|
---|---|
Authors: | Hordijk, Wim ; Shalizi, Cosma Rohilla ; Crutchfield, James P. |
Institutions: | Santa Fe Institute |
Saved in:
Saved in favorites
Similar items by person
-
Computational Mechanics: Pattern and Prediction, Structure and Simplicity
Shalizi, Cosma Rohilla, (1999)
-
Mechanisms of Emergent Computation in Cellular Automata
Hordijk, Wim, (1998)
-
Comments on ``Simple Measure for Complexity''
Crutchfield, James P., (1999)
- More ...