Universality in Cellular Automata
Universality in Cellular Automata
复制标题
元胞自动机的普遍性
DOI：
10.1109/swat.1970.27
复制
发表时间：
1970
期刊：
影响因子：
--
通讯作者：
E. R. Banks
中科院分区：
文献类型：
--
作者：
E. R. Banks
机器的复杂行为可以通过拥有大量非常简单的机器来实现，也可以通过拥有一个复杂的机器来实现。我们对这篇论文的主要兴趣是前者。通过考虑大量最简单机器的全局行为，得到了如下结果：1。一个由相同的正方形单元组成的阵列，每个单元只能以四种状态存在，并与它的四个最近的邻居（形成一个由五个单元组成的邻居）进行通信，它可以a）执行任何可计算的计算，B）构造（几乎）任何配置-特别是，它可以自我复制。具有第一种行为的单元被称为通用计算机;第二种行为是通用构造器的特征。2.当配置在有限的初始区域中时，三个状态、五个相邻单元能够进行通用计算。3.两个状态和五个邻居足以进行通用计算，但需要无限的初始配置。作为并行机，这些元胞自动机可以作为并行计算的良好理论基础，并且在许多与图灵机相同的领域中应该是有用的。还指出了实际的物理应用。
Complex behavior by machines can be achieved by either having a large number of very simple machines or by having a complex machine with which to start. Our primary interest in this paper was with the former. By considering the global behavior of a large number of the simplest of machines, the following results were shown: 1. An array of identical square cells each of which can exist in only four states and communicates with its four nearest neighbors (forming a neighborhood of five cells) can a) perform any computation which is computable and b) construct (almost) any configuration--in particular, it can be self-reproducing. Cells capable of the first behavior are called universal computers; the second behavior characterizes the universal constructor. 2. A three state, five neighbor cell is capable of universal computation when configured in a finite initial area. 3. Two states and five neighbors are sufficient for universal computation, but require an infinite initial configuration. Being parallel machines, these cellular automata can serve as a good theoretical basis for parallel computation and should be useful mathematically in many of the same areas as the Turing Machine. Practical physical applications were also indicated.