Self-reproduction in asynchronous cellular automata
Self-reproduction in asynchronous cellular automata
复制标题
异步元胞自动机中的自我复制
DOI：
10.1109/eh.2002.1029886
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Chrystopher L. Nehaniv
中科院分区：
文献类型：
--
作者：
Chrystopher L. Nehaniv
基于冯·诺依曼、伯克斯、科德和兰顿等人的工作，我们介绍了元胞自动机中异步自我复制的第一个例子。自从半个世纪前冯·诺依曼首次提出元胞自动机实现自我生产的问题以来，对全局同步更新信号的依赖一直是所有解决方案的限制。我们的结果消除了这种限制的需要。我们引入了一种简单的构造机制，将任何具有同步更新的元胞自动机网络转换为具有相同行为但其元胞可以随机和异步更新的元胞自动机网络。这是通过引入同步底层来实现的，该同步底层以保持所有单元本地同步的方式本地跟踪本地邻域中的时间流逝。该机制的通用性由一个通用数学定理（由作者提出）保证，该定理允许异步实现任何同步元胞自动机配置和规则，从而可以从相应的异步元胞自动机的行为中恢复原始同步元胞自动机的行为。因此，过去获得的关于自我复制、通用计算、通用构造以及元胞自动机中自我复制配置群体进化的所有重要结果都延续到了异步领域。
Building on the work of Von Neumann, Burks, Codd, and Langton, among others, we introduce the first examples of asynchronous self-reproduction in cellular automata. Reliance on a global synchronous update signal has been a limitation of all solutions since the problem of achieving self-production in cellular automata was first attacked by Von Neumann half a century ago. Our results obviate the need for this restriction. We introduce a simple constructive mechanism to transform any cellular automata network with synchronous update into one with the same behavior but whose cells may be updated randomly and asynchronously. This is achieved by introduction of a synchronization substratum which locally keeps track of the passage of time in a local neighborhood in a manner that keeps all cells locally in-step. The generality of this mechanism is guaranteed by a general mathematical theorem (due to the author) that allows any synchronous cellular automata configuration and rule to be realized asynchronously in such a way the the behavior of the original synchronous cellular automata can be recovered from that of the corresponding asynchronous cellular automaton. Thus all important results on self-reproduction, universal computation, and universal construction, and evolution in populations of self-reproducing configurations in cellular automata that have been obtained in the past carry over to the asynchronous domain.