Turing Universality of the Game of Life
Turing Universality of the Game of Life
复制标题
生命游戏的图灵普遍性
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Paul W. Rendell
中科院分区：
文献类型：
--
作者：
Paul W. Rendell
本章介绍了一个图灵机建立模式的康威的游戏生命细胞自动机。它概述了建筑的架构、其部件的结构并解释了机器的工作原理。它还说明了在设计过程中所做的原则选择0 [17]。关于图灵机，最小通用图灵机（模拟任何其他图灵机的图灵机）和非擦除图灵机的背景信息可以在[20，7，15，14，18]中找到。图灵机的重要性在于通用图灵机的存在。因此，一台能模拟任何图灵机的机器就能模拟一台通用图灵机。已经证明图灵机可以被许多类型的机器模拟：元胞自动机（如本书本章和其他章节所示），随机存取机[4]，寄存器机[1]等。特别是Minsky [16]描述了一种可以模拟图灵机的寄存器机。这种寄存器有一个不寻常的特性，能够存储任何大小的正数。值得注意的是，很久以前，康威在《生命的游戏》中描述了一种构造这种形式的寄存器的方法。这将在本章后面部分讨论。
This chapter describes a Turing machine built from patterns in the Conway’s Game of Life cellular automaton. It outlines the architecture of the construction, the structure of its parts and explains how the machine works. It also illustrates the principle choices made during the design0 [17]. Background information about Turing machines, minimal universal Turing machines (those that simulate any other Turing machine) and non-erasing Turing machines can be found in [20,7,15,14,18]. The importance of Turing machines is the existence of universal Turing machines. Thus a machine that can simulate any Turing machine can simulate a universal Turing machine. It has been proved that Turing machines can be simulated by many types of machine: cellular automata (as one can see in this and other chapters of this book), random access machines [4], register machines [1] and others. In particular Minsky [16] describes a register machine which can simulate a Turing machine. The registers have the unusual property of being able to store positive numbers of any size. Remarkably, a long time ago Conway described [1] a method of constructing a register of this form in the Game of Life. This is discussed later in this chapter.