Complexity Classes in the Two-dimensional Life Cellular Automata Subspace
Complexity Classes in the Two-dimensional Life Cellular Automata Subspace
复制标题
二维生命元胞自动机子空间中的复杂性类别
作者：
Michael Magnier;C. Lattaud;J. Heudin
元胞自动机（CA）是一类离散动力学模型，它代表了对由大量简单和局部相互作用元素组成的物理系统的近似[18]。它们因其丰富多样的现象学而引起了许多研究者的兴趣[16]。在这个框架中，Wolfram已经证明CA表现出全谱的动力学行为[19]，并提出了将其动力学定性分类为四组[20]。I类与相空间中的极限点相关联;对于几乎所有的配置，细胞元素在相对较短的瞬态周期后具有相同的值。第二类是与极限环;几乎所有的配置导致一个均匀的状态，除了一些稳定和振荡模式。第三类与混沌行为有关，指的是明显不可预测的时空行为。IV类与以长瞬态和传播模式的存在为特征的复杂行为相关联。此外，一些IV类CA被怀疑支持通用计算。
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.