在生命的最后几年，冯·诺依曼问了自己一个听起来像哲学的问题：机器能造出自己的副本吗？困难在于逻辑。要造出副本，机器需要一份关于自己的描述；可描述又是机器的一部分，于是它还得描述这份描述，如此下去，陷入无穷倒退。

描述、构造器和复制器

冯·诺依曼在 1948 年起的讲座中提出的出路，是把三个部分分开：

  1. 构造器 $A$，读取任意机器 $X$ 的描述 $D(X)$，并造出 $X$；
  2. 复制器 $B$，复制任何描述，而不需要理解它；
  3. 控制器 $C$，把两者连接起来。

现在把机器 $A + B + C$ 自己的描述 $D(A + B + C)$ 交给它。构造器读取描述，造出一台新的机器 $A + B + C$；复制器把描述复制一份，交给新机器。结果是一个完整的副本，带着它自己的描述。倒退之所以终止，是因为描述被以两种方式使用：一次作为要执行的指令，一次作为不加阅读就复制的文本。

格子网格

为了让这个想法变得严格，冯·诺依曼需要一个可以在其中搭建机器的简单“宇宙”。在乌拉姆的建议下，他使用了一个由小方格组成的无穷网格，每个方格处于 29 种状态之一，所有方格在每一步同时根据四个邻居的状态而改变。他在这个网格中设计了一个巨大的构型，包含数量极其庞大的格子，能够读取一条带子、造出自己的副本并复制这条带子。这项工作在他去世时尚未完成，由他的合作者阿瑟·伯克斯补全，并于 1966 年以《自我复制自动机理论》为题出版。

斯坦尼斯瓦夫·乌拉姆在洛斯阿拉莫斯的证件。正是乌拉姆向冯·诺依曼建议用格子网格作为机器的宇宙。
斯坦尼斯瓦夫·乌拉姆在洛斯阿拉莫斯的证件。正是乌拉姆向冯·诺依曼建议用格子网格作为机器的宇宙。Los Alamos National Laboratory · Wikimedia Commons · 公有领域

这样的网格今天称为元胞自动机。1970 年，英国人约翰·康威发明了一个只有两种状态（活和死）的元胞自动机，规则只有一行：有 2 个或 3 个活邻居（算上对角线）的活格存活；恰好有 3 个活邻居的死格诞生；其余的死亡或保持死亡。康威称之为生命游戏，它丰富到在其中也能搭建计算机和自我复制的机器。

练习：闪烁器

在生命游戏中，横排的三个活格构成“闪烁器”。证明下一步它们会变成竖排。

中间的格子有 2 个活邻居，存活。两端的格子只有 1 个活邻居，死亡。中间格子正上方和正下方的两个格子恰好有 3 个活邻居（横排的三个），诞生。结果：竖排的三个。同样的推理表明，再下一步它又变回横排，这个图案永远闪烁下去。

练习：为什么要复制器？

冯·诺依曼的机器为什么需要复制器 $B$？让构造器 $A$ 把描述也造出来不就行了吗？

要根据指令造出描述，描述就必须包含对它自身的描述，而那又包含另一份描述，如此下去：正是开头那个无穷倒退。复制器避免了这一点：它把描述当作一串符号来复制，不需要另一份描述。

来源： John von Neumann, “The general and logical theory of automata”（1948 年讲座，1951 年发表）· John von Neumann 与 Arthur W. Burks（编）, Theory of Self-Reproducing Automata（1966）· Martin Gardner, “The fantastic combinations of John Conway’s new solitaire game ‘life’”, Scientific American（1970）。

约翰·冯·诺依曼的全部主题 · ← 变公平的不公平硬币 · 约翰·冯·诺依曼的遗产 →

图片来源.