Upper Bound on the Products of Particle Interactions in Cellular Automata

Wim Hordijk, Cosma Rohilla Shalizi and James P. Crutchfield

Working Papers from Santa Fe Institute

Abstract: 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

Date: 2000-09
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wop:safiwp:00-09-052

Access Statistics for this paper

More papers in Working Papers from Santa Fe Institute Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Krichel (krichel@openlib.org).