THERMODYNAMICS AND COMPLEXITY OF CELLULAR-AUTOMATA

The complexity exhibited by cellular automata is studied using both to pological (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 rule s and that this asymptotically yields a phase transition when the ther modynamic formalism is applied to the limit spatial configuration.