Complexity Classes in the Two-dimensional Life Cellular Automata Subspace.
Michael Magnier, Claude Lattaud, Jean-Claude Heudin · Complex Systems · 1997
Cellular automata (CA) are a class of discrete dynamical models which represent an approximation to physical systems composed of a large number of simple and locally interacting elements [18]. They have caught the interest of many researchers because of their rich and diverse phenomenology [16]. In this framework, Wolfram has shown that CA exhibit the full spectrum of dynamical behaviors [19] and proposed a qualitative classification of their dynamics into four groups [20]. Class I is associated to limit points in the phase space; for almost all configurations, cellular elements have the same value after a relatively short transient period. Class II is associated to limit cycles; almost all configurations lead to an homogeneous state, except for some stable and oscillating patterns. Class III is associated to chaotic behaviors which refer to apparently unpredictable space-time behaviors. Class IV is associated to complex behaviors characterized by long transients and the existence of propagating patterns. Also, some Class IV CA are suspected to support universal computation.