Thermodynamics and complexity of cellular automata

Year: 1997

Authors: Badii R., Politi A.

Autors Affiliation: Paul Scherrer Institut, Villigen, Switzerland;
Istituto Nazionale di Ottica, Largo E. Fermi 6, 50125 Firenze, Italy;
Istituto Nazionale di Fisica Nucleare, Sezione di Firenze, Italy

Abstract: The complexity exhibited by cellular automata is studied using both topological (graph-theoretical) and metric (thermodynamic) techniques. A novel topological classification, based on a hierarchy of languages, is introduced. In particular, it is shown that the elementary rule 22 is able to produce, upon iteration, a deep nesting of grammatical rules and that this asymptotically yields a phase transition when the thermodynamic formalism is applied to the limit spatial configuration.

Journal/Review: PHYSICAL REVIEW LETTERS

Volume: 78 (3)      Pages from: 444  to: 447

KeyWords: Dynamic-systems; Attractors
DOI: 10.1103/PhysRevLett.78.444

Citations: 23
data from “WEB OF SCIENCE” (of Thomson Reuters) are update at: 2024-11-17
References taken from IsiWeb of Knowledge: (subscribers only)
Connecting to view paper tab on IsiWeb: Click here
Connecting to view citations from IsiWeb: Click here