Thermodynamics and complexity of cellular automata

R Badii, A Politi

Research output: Contribution to journalArticlepeer-review

24 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)444-447
Number of pages4
JournalPhysical Review Letters
Issue number3
Publication statusPublished - 20 Jan 1997




Dive into the research topics of 'Thermodynamics and complexity of cellular automata'. Together they form a unique fingerprint.

Cite this