此文原本是我在触乐网的《〈群星〉〈无敌号〉中描述的自我复制机器是什么？》（cv8018038）一文下面的评论，经过了一些扩写，补充了一些图片。
题图来自维基共享资源，作者 Peter J. Yost。
冯·诺伊曼提出自我复制机器的构想，是在 1948 年的一次演讲中——演讲的内容后来被整理成论文《The General and Logical Theory of Automata》。
他所构想的机器，或者叫自动机（Automata），由 ABC 三个部分组成：
部分 A 是一台用来制造机器的机器。只要你给它输入合适的指令和充分的材料，它就能根据指令构造出任意的机器。这一部分又被称为通用构造器（Universal constructor）。
部分 B 的工作很简单：把任何指令复制一份。
部分 C 负责控制整个机器的运行。在它的控制下，当机器收到一段指令的时候，A 会根据指令构造出一台机器，然后 B 会把指令复制一份，复制出来的指令又会被传给 A 刚造出来的机器。
现在，只要能找到一段用来构造 A+B+C 的指令 I，并把它传给机器，机器就能无限复制下去了。只要修改指令，机器还能在复制的同时生产别的东西。
这一构想和生物的中心法则有着异曲同工之妙：DNA 扮演了这里的指令 I 的角色；而 DNA 的复制、转录、翻译成蛋白质，所需的各种酶则可对应于机器的各个部分。
但当时中心法则还未被发现。为了证明自己的构想可行，冯·诺依曼和波兰数学家 Stanislaw Ulam——喜欢数论的朋友可能听说过他的乌拉姆螺旋——一起，提出了一个新的数学模型：元胞自动机（Cellular Automata）。
元胞自动机的世界是一个无限的正方形网格，每个格子称为一个“细胞”，每个细胞都处于某种状态。在每个回合中，每个细胞会按照同样的规则，根据本身的状态和“邻居”的状态来改变自己的状态。
一个蓝色的细胞，和它的四个红色的邻居。在有的规则下，邻居的范围可以更大，比如包括四个粉红色的鸽子。图片来自维基共享资源，作者 Torchiest。
这一模型确实适合实现冯·诺依曼的构想：无限多的细胞，可以作为构造机器的材料。机器可以由细胞搭建而成，指令也可以由一长串不同状态的细胞来表示。
冯·诺依曼设计了一套相当复杂的元胞自动机规则，每个细胞有多达 29 种可能的状态。他没有真的构造出一台自我复制机，只是证明了它的存在——当然，对于数学家来说，证出来比造出来更重要。直到 1995 年，Renato Nobili 和 Umberto Pesavento 才真正实现了这一构想，不过他们所用的规则与冯·诺依曼原本的规则略有不同，细胞的状态达到了 32 种。又过了几年，William Buckley 在冯·诺依曼原本的规则中也造出了自我复制机。
Nobili 和 Pesavento 的自我复制机。指令储存在右侧的长条中，其细胞数要远远超过左侧的机器主体部分，图片只显示了它的一小部分。图片来自维基共享资源。
冯·诺依曼之后的数学家试着简化这一套规则。比如说，Edgar Codd 在 1968 年提出的规则只有 8 种状态，不过他也没能实际构造出一个自我复制机。再往后，Christopher Langton 在 1984 年构造出了名为 Loops 的元胞自动机，同样是 8 种状态，只需 86 个细胞就能实现自我复制。不过，他已偏离了冯·诺依曼的道路：这一“机器”并不符合冯·诺依曼提出的架构，不包含通用构造器，除了自我复制，什么都不能干。
Loops 自我复制的过程还挺好看的：
图片来自 Adam P. Goucher 的博客：cp4space.hatsya.com
元胞自动机火出圈外，靠的还是康威的生命游戏。
生命游戏的规则特别简单，每个细胞只有两种状态：死和活。“邻居”的定义是环绕细胞的8格。每一回合中：
如果一个活细胞有2个或3个邻居活着，则保持活着；
如果一个死细胞有3个邻居活着，则会活过来；
其他情况下细胞都会死去。
这么简单的规则也能构造出自我复制机吗？
最初，康威本人也不知道这简单的规则后面隐藏着怎样的复杂性。他悬赏50美元来寻找第一个无限增长的图样。获得这50美元的是 Bill Gosper：他发现了一种称为“滑翔机枪”的图样，能周期性地发射一种叫“滑翔机”的简单图样。
Gosper 的滑翔机枪。图片来自 LifeWiki。
更妙的是，把八架滑翔机撞在一起，就能合成一把新的滑翔机枪：
用滑翔机合成滑翔机枪。图片为自制，合成配方来自 Catagolue。
滑翔机能撞出枪，就能撞出别的东西。这种用滑翔机合成其他图样的机制，称为“滑翔机合成反应”（Glider synthesis）。这正是通用构造器所需要的反应。于是，我们只需要设计出这样一台机器，它能根据输入的指令，在指定的时间，指定的地点，往指定的方向发射滑翔机。而指令本身也可以由一长串的滑翔机组成。
按此思路，康威在 1982 年证明了生命游戏的世界中也存在着通用构造器和自我复制机。他的证明可以在《Winning Ways for Your Mathematical Plays》一书中找到。当然，也只有证明，没有实际的构造。直到 2013 年，Dave Greene 才构造出生命游戏中的第一台自我复制机。
Dave Greene 的自我复制机的局部。图片来自 LifeWiki。
生命游戏中的自我复制机极为复杂，构造起来非常困难。但在一些与生命游戏接近的元胞自动机规则中，自我复制的图样却极为常见，复制的方式也多种多样。比如说，只要把生命游戏规则的第二条改成：
如果一个死细胞有3个或6个邻居活着，则会活过来；
得到的规则称为 HighLife。这个规则中有一个非常简单、非常常见，又能自我复制的图样。它太简单了，很难称得上是一台机器：
HighLife 的自我复制机。图片来自 LifeWiki。
再比如说，如果把生命游戏的规则改成：
不管细胞本身的状态；
如果一个细胞有奇数个邻居活着，下一回合它也会活着；
如果一个细胞有偶数个邻居活着，下一回合它会死去。
在这个规则下，所有的图样都会自我复制！
一个点在上述规则中的自我复制。图片为自制。
能不能在生命游戏中也实现这种形式的自我复制？
想法很简单：只要在生命游戏中构造一种模拟别的元胞自动机的机器就可以了。
用生命游戏模拟别的元胞自动机并不是什么新鲜事，比如说著名的 OTCA metapixel（参见 BV1ws411f7Xn，那里模拟的是生命游戏本身，但它也能模拟别的元胞自动机）。但在 OTCA metapixel 中，代表死细胞的不是空白，而是处于另一种状态下的 OTCA metapixel。我们要先用许多个 OTCA metapixel 搭建出一个舞台，才能在上面模拟别的元胞自动机。这样的机器并不适合用来实现自我复制。
于是，这台机器本身就需要有自我复制的能力。它模拟的只是活细胞，死细胞则由空白的空间来代表。它必须通过自我复制来产生新的细胞，死亡则通过自我拆除来实现。
最终实现这一构想的是 Adam P. Goucher。2018 年，他构造出了 0E0P metacell——一个由超过一千万个细胞组成的庞然大物。它的具体介绍可以在 Goucher 的博客文章《Fully self-directed replication》（https://cp4space.hatsya.com/2018/11/12/fully-self-directed-replication/）中找到，该文也是我这篇文章最主要的参考资料之一。
有趣的是，0E0P metacell 并没有获选 2018 年的生命游戏年度图样。在投票评选中，它输给了 Sir Robin ——生命游戏中的第一个初等的“马行船”（knightship），这样的图样和滑翔机一样会周期性地平移，但前进的方向是和象棋中的马一样走日字。0E0P metacell 又以微弱的优势领先于另一个发现：每一个能通过滑翔机合成反应来构造的图样，都可以用不超过 35 架滑翔机来合成。这三者都是 Adam P. Goucher 的作品。
