初等元胞自动机的全计算相关拓扑动力学分类。
A full computation-relevant topological dynamics classification of elementary cellular automata.
机构信息
Institute of Neuroinformatics, ETH and University of Zurich, 8057 Zurich, Switzerland.
出版信息
Chaos. 2012 Dec;22(4):043143. doi: 10.1063/1.4771662.
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."
元胞自动机既是计算系统也是动力系统。我们基于基本动力系统概念，如敏感性和混沌性，对基本元胞自动机（ECA）的动态行为进行了全面分类。“复杂”的 ECA 是敏感的，但不是混沌的，也不是最终的弱周期性的。基于这种分类，我们推测，能够进行复杂计算的基本元胞自动机，如图灵通用性所需的计算，处于“混沌边缘”。
Zotero 插件