Thermodynamics and complexity of cellular automata
Anno: 1997
Autori: Badii R., Politi A.
Affiliazione autori: 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.
Giornale/Rivista: PHYSICAL REVIEW LETTERS
Volume: 78 (3) Da Pagina: 444 A: 447
Parole chiavi: DYNAMIC-SYSTEMS; ATTRACTORS; DOI: 10.1103/PhysRevLett.78.444Citazioni: 23dati da “WEB OF SCIENCE” (of Thomson Reuters) aggiornati al: 2024-05-12Riferimenti tratti da Isi Web of Knowledge: (solo abbonati) Link per visualizzare la scheda su IsiWeb: Clicca quiLink per visualizzare la citazioni su IsiWeb: Clicca qui