A full computation-relevant topological dynamics classification of elementary cellular automata.
A full computation-relevant topological dynamics classification of elementary cellular automata.
复制标题
基本元胞自动机的完整计算相关拓扑动力学分类。
作者：
Martin Schüle;R. Stoop
元胞自动机既是计算系统，又是动力学系统。根据基本的动力学系统概念，如敏感性和混沌，我们给出了基本元胞自动机(ECA)的动态行为的完整分类。“复杂的”ECA看起来很敏感，但并不混乱，最终也不是弱周期的。基于这种分类，我们推测，能够执行复杂计算的基本元胞自动机，如图灵普适性所需的，处于“混乱的边缘”。
Cellular automata are both computational and dynamical systems. We give a complete classification of the dynamic behaviour of elementary cellular automata (ECA) in terms of fundamental dynamic system notions such as sensitivity and chaoticity. The "complex" ECA emerge to be sensitive, but not chaotic and not eventually weakly periodic. Based on this classification, we conjecture that elementary cellular automata capable of carrying out complex computations, such as needed for Turing-universality, are at the "edge of chaos."