Upper bound on the products of particle interactions in cellular automata

PHYSICA D-NONLINEAR PHENOMENA

卷:154

Article

Hordijk, W ; Shalizi, CR ; Crutchfield, JP

关键词: cellular automata;    particles;    gliders;    domains;    particle interactions;    domain transducer;   

DOI  :  10.1016/S0167-2789(01)00252-4

来源: Elsevier

【 摘 要 】

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 elucidating 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. (C) 2001 Published by Elsevier Science B.V.

【 授权许可】

Free