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.
Original language | English |
---|---|
Pages (from-to) | 444-447 |
Number of pages | 4 |
Journal | Physical Review Letters |
Volume | 78 |
Issue number | 3 |
Publication status | Published - 20 Jan 1997 |
Keywords
- DYNAMIC-SYSTEMS
- ATTRACTORS