递归宇宙

几年前，我偶然看到这个视频，它展示了一台复杂的机器，完全是在康威的“生活的游戏”(Game Of Life)中制作的：

该机器的目的是模拟单个生命像素。有了这些“元素”的足够大的矩阵，你就可以在大规模上模拟生命的元版。在此基础上，您可以从元元创建一个元元，等等…。。

当时我正在读威廉·庞德斯通(William Poundstone)的“递归宇宙”(The Recursive宇宙)一书，书中详细分析了约翰·康威(John Conway)1982年所著的“生命中自我复制对象的证明”。自1970年问世以来，康威的“生活游戏”已经发展了一批研究人员、工程师和业余爱好者的狂热追随者，他们相互推动，用屏幕上的像素建造越来越精致的“机器”。这些研究已经导致了对主题、反应和机制的冗长分类，以及工程原理和设计抽象。如今，你可以花很长时间在YouTube上探索人们在“简单的”生活世界中设计的看似不可能的事情。

这篇帖子(大部分)是我在2015年试图理解这个元素是如何设计的时做的一些笔记。不幸的是，约翰·康威最近去世了，这让我再次思考生活(不要听起来太伤感)。现在我发现自己手头有很多时间，我想我应该清理一下这些笔记，最后开始写这个博客(第一篇文章！)。

康威的“生活游戏”是一个2D细胞自动机--一个设置在像素(细胞)网格上的模拟世界。尽管管理生活的规则很简单，但结果可能会变得相当复杂。在生命的游戏中，细胞的行为由它的当前状态(活着还是死了)和它最近的八个邻居的状态决定。“生活法则”松散地基于人口动态(抄袭自下面的维基百科)：

任何少于两个活邻居的活细胞都会死亡，就好像是由于人口不足造成的。

任何有两三个活邻居的活细胞都会传到下一代。

恰好有三个活的邻居的任何死亡细胞都会变成一个活细胞，就好像是通过繁殖一样。

生活中最有趣的事情之一就是可以在生活中构建各种各样的模式。在野外很容易观察到一些模式--自发地从活细胞和死亡细胞的随机汤中涌现出来。其他模式是由人们精心设计的，通常由具有良好特征的行为的较小的子单元构建。一般说来，生活中的模式可以分为几大类，如下所述。(图片来源：维基百科)。

“振荡器”是在一定数量的时间步长之后重复自身的动态模式：

“宇宙飞船”是一种振荡器，当它振动时会在空间中移动。最简单、最普通的宇宙飞船(这里的“普通”指的是它经常在野外出现)被称为“滑翔机”：

其他常见的宇宙飞船是轻型宇宙飞船，以及它的兄弟，中型和重型品种：

“Guns”指的是产生一连串宇宙飞船的结构；Gosper的滑翔机枪是迄今发现的第一把枪：

“反应”是产生有用结果的生命对象的碰撞。滑翔机合成是一个仅通过滑翔机的碰撞来创造生命模式的过程。滑翔机合成形成了已知的和积极研究的生命反应的一个很大的子集，它是康威证明生命中存在自我复制机器的关键。这是3架滑翔机合成的一艘中等重量的宇宙飞船：

使用宇宙飞船、静物、振荡器、枪支以及它们之间的反作用的组合，就有可能在生活中建造出令人难以置信的复杂机器。以下是使用一系列定时滑翔机碰撞来建造60P5H2V0宇宙飞船的Period 416炮的示例：

Life中其他值得注意的工程成就包括Gemini(由长滑翔带编码的宇宙飞船)、线性传播器(自我复制机器)、图灵机、Minsky寄存器机器(有限通用计算机)和otca Metapixel(一种行为类似于大规模Life像素的结构，也是本文剩余部分的主题)。

2006年，Brice Due发表了otca Metapixel，这是一个2058x2058的细胞结构，模拟了单个生命细胞的行为。Otca元素不是Life中设计的第一个、最小或最快的元素(也可以查看P5760 unit Life单元格和Deep单元格)，但它有一个有趣的特性，即缩小时看起来像单个生命细胞。它还有一个寄存器，允许您根据任何类似于生命的任意元胞自动机规则集对其行为进行编程。

在本文的其余部分中，我将描述元素的内部工作方式。我所有的信息都来自生活维基，otca网站，生活词典。(主要)下载Golly并观看otca Metapixel运行。

像大多数计算机处理器一样，otca元像素由一个中央时钟驱动，该时钟调节其事件的时间。时钟由拖拉机光束提供动力，这是一系列宇宙飞船，慢慢地将物体拉向其源的方向(一个简单的例子是面包拖拉机光束-其中一条面包被逐渐拉向进入的轻质宇宙飞船流)。

在上面的视频中，拖拉机光束在每次碰撞中将一个积木向下拉8个单元，每次向右释放一架滑翔机。由食肉1s制成的拖拉机横梁一侧的栅栏会立即摧毁滑翔机，但栅栏上有几个洞，允许滑翔机以精确的时间间隔穿过元像素并与其他结构相互作用。

在视频中大约0点57分，你可以看到拖拉机光束发射三架滑翔机越过围栏进入一个名为“LWSS包枪”的结构中；这释放了三组三个轻型宇宙飞船(LWSS)，每架迎面而来的滑翔机一组。稍后，大约1：21，您可以看到又有四架滑翔机从拖拉机光束发射到象素中。第一个滑动器启动邻居计数解码序列，接下来的两个滑动器从解码器读取结果，最后一个滑动器启动逻辑级联，最终决定在下一个时钟周期中打开还是关闭元像素(所有这些都在后面更详细地描述)。图中总结了7架滑翔机的作用。

最后，块在拖拉机光束的源处被破坏，并恢复到其起始位置，再次开始循环。

元像素的规则编码为两列(类似于硬件寄存器)，如下图所示：

类似生命的自动机规则是以B#/S#的形式编写的，这里描述了这一点。Conway的规则定义为B3/S23，因此OTCA元像素的相应寄存器位各填充一个-1\f25 Eater-1\f6(-1\f25 Eater-1\f6)：

在每个时钟周期中，三组LWSS(总共9组)离开LWSS数据包枪(由时钟触发，如上所述)，并完成围绕元像素的循环，途中经过每个元像素的摩尔邻居。当LWSS经过每个邻居时，如果该邻居当前处于“活”状态，则列车中的第一艘船会与其路径上的一个池塘相撞；这种碰撞会使该船失效，并使列车中的船舶总数减少1。如果邻居不活着，那么池塘就不存在了，船只就会安然无恙地驶过。由于火车从9个LWSS开始，如果一个元素有4个活动的邻居，那么在完成一次环绕周边的传递后，只有5个LWSS会返回。下面显示了一列LWSS在大约0：26与一个池塘相撞的情况(稍后我将解释池塘是如何到达那里的)：

这段视频还展示了双蜜蜂航天飞机和其他反射器围绕元素的LWSS列车的牧羊人，以及一对滑翔炮对舰艇(略微改变相位)进行“色彩调整”的例子。此图显示了LWSS的路径以及调色器和可能的池塘的位置。

LWSS列车的完整路径如下所示。请注意，当火车经过每个活着的邻居时，一艘船是如何从火车前部移走的。

当LWSS序列完成环路时，它们被导入一个机制(同步缓冲器和p46到p40转换器)，在那里它们给出相同的相位。然后，它们被发送到规则寄存器，在那里它们与来自相反方向的另一个LWSS(源自时钟外的滑翔机之一)发生碰撞，以将LWSS序列解码为活着的邻居的数量(如下图所示)。

从时钟开始的LWSS列车和LWSS之间的碰撞位置取决于在围绕元像素的循环期间从列车前面破坏了多少LWSS。这个机制是这样设置的，即碰撞向相反方向发射出两架滑翔机，瞄准的寄存器与元素的活着邻居的数量相对应(同样，请参阅这张图片作为参考)。

通常情况下，滑翔机都会与蜂巢相撞，形成一个积木和一个池塘，这被称为蜂巢反应。如果你从大约6：00观看到上面的视频，你会看到反平行的LWSS的碰撞，将两架滑翔机送往出生和生存寄存器中的第四个槽(从底部开始向上计数，从0开始)，大约6：30在寄存器中形成了两个池塘。LWSS列车中剩余的宇宙飞船与食人一号相撞，并被摧毁。下面的视频展示了几代人的近距离观察：

如果寄存器中的槽被食者-1占据(正如出生寄存器中的第三个槽，以及存活寄存器中的第二个和第三个槽，再次从底部开始从0开始计数)，那么进入的滑翔机在它有机会发起与蜂巢的蜜位反应之前就被摧毁了。这不会在收银机中产生池塘。在这种机制中，如果居住的邻居的数量不满足下一代生活的条件，登记册就会有一个池塘，如果满足了，就没有池塘。请记住，此信息分为两个寄存器(出生和存活)，在后面的步骤中，一些逻辑将查看元像素的当前状态，以确定要从哪个寄存器读取(稍后描述)。这种机制使得otca元素可以为任何类似于Life的规则集编程，非常酷。

接下来，时钟发出一对LWSS来读取这些寄存器(每个寄存器一个LWSS)，如图所示。如果寄存器中存在池塘，则LWSS会与池塘发生碰撞并被破坏。这就完成了蜜位反应，并将蜂箱恢复到其原始状态。如果LWSS的路径中没有池塘，则允许其继续进入下一个逻辑库。在上面的视频中，看看是否可以通过读取寄存器来预测元像素的下一状态。

在我进入系统的最后一个逻辑之前，让我们先看看邻居状态是如何统计的。此图显示了每个元素的8个输入/输出通道，每个通道对应于单个元素的八个邻居之一。通过仔细观察其中的一个，您将看到另一个蜜位反应正在发生：

左侧的蜜位反应对应于右侧的元像素的状态，右侧的反应对应于左侧的元像素的状态。LWSS列车绕着图元顺时针方向移动，因此沿着屏幕向下移动的列车属于左侧的像素，沿屏幕向上移动的列车属于右侧的像素。

这些蜜比特反应是由中等重量的宇宙飞船(MWSS)设定的，它在每个时钟周期围绕像素以逆时针方向移动。这里描述了它的路径，以及它为元素周围的8个蜜位反应生成的所有滑翔机的路径。只有当元像素的当前状态是活动的，并且在其围绕像素的循环结束时，才会创建MWSS。

从一系列逻辑门读取系统的最终状态。正如在前面的一些部分中已经演示过的，生活中的逻辑通常是通过发送宇宙飞船(通常是滑翔机)通过一条路径来实现的，在该路径中，它们可能会也可能不会与其他物体相撞并被湮灭。在他们的旅程结束时，一个阅读机制测试他们是否存在(1)或不存在(0)。下面的视频显示了各种布尔运算的一些具体示例。长长的“滑翔机磁带”甚至可以用作永久存储器来存储大量信息，双子座和这个可编程文本生成器(“Golly Ticker”)就展示了这一点。

B是出生登记簿的状态，1表示满足出生条件，0表示不满足。

C、B和S的状态通过三艘船的存在(“1”)或不存在(“0”)存储在元像素中。船有一个有趣的特性，当它们被滑翔机击中时，它们会反射出一架新的滑翔机，其轨迹与即将到来的滑翔机的轨迹垂直。这种碰撞会毁掉船，所以船被称为一次性反射器。在上述解码步骤中，使用能够通过出生和生存寄存器的LWSS来设置B和S船(如图所示)。在这段视频中，观看一对LWSS如何将船放置在B和S位置，从3：47开始，它们设置的时刻是4：52：

滑翔机用于读取C、B和S的状态，并将池塘设置在G或H(如下图所示)。G和H池塘形成的逻辑(“1”表示形成池塘，“0”表示没有池塘)由以下逻辑给出：

G=C&；！S(当C为1且S为0时，G等于1，否则G为0)

H=！C&；B(当C为0且B为1时，H等于1，否则H为0)。

时钟释放的最后一个滑块(在开头描述)引发了计算这些关系的逻辑级联。滑翔机通过时钟旁边栅栏上的小孔释放，距离上面视频左侧不到一半(15：45)，触发形成一个向视频右侧飞行的LWSS(15：48)，在途中释放了两架滑翔机(16：11)。第一个滑翔机弹来弹去，最终变成了一个LWSS，它读取G和H的结果，下一段将详细介绍这一点。第二只滑翔机朝C飞去，如果C存在，它会反射并开始朝S飞去。如果S存在，它就会反射到食者身上并死亡，如果S不存在，它就会继续在G处形成蜂巢，并进行蜜位反应，形成一个池塘。如果C不存在，则第二个滑翔机改为朝向B。如果B存在，滑翔机就会反射B并在H处进行蜜位反应，否则它就会撞上食肉动物而死。在上面的视频中，从16点20分开始，我们看到滑翔机正在创建，从C反射过来，穿过没有的S，最后在G处形成一个池塘。

在16：37，您可以看到一个池塘设置在G处，LWSS从左侧进入，读取G和H。如果G或H中的任何一个设置了池塘，则LWSS被破坏，如16：39所示。如果两者都没有设置(见10：47)，则LWSS继续，并在！T处形成一条船(在此图中显示为T，顶部有一条线)。这可以用下面的逻辑来概括：

！t=！(G|H)(！t在G和H均为0时等于1，否则！t为0)。

第三架滑翔机在10点56分由最初的LWSS触发器释放，朝T方向飞去。如果T处有船，滑翔机就会反射出船，撞上食肉动物，如果船不在，它会继续到T(同样，如图所示)。滑翔机在11：17被食者摧毁，但你可以看到它变成了LWSS，并在5：33开始的前一次迭代中前往T。

第四架滑翔机由原来的LWSS释放，它变成LWSS，在逻辑运算完成后清理任何留在B或S的剩馀船只。示例从5：23开始。这个LWSS没有其他功能，它要么被它清理的船摧毁，要么被食者摧毁。它的轨迹显示在这里。

T=在T处存在LWSS，则该状态的形式逻辑由下式给出：

T=！(！t)=G|H=(C&；！s)|(！C&；B)

如果像素当前是活的并且不满足生存要求，或者如果像素当前是死的并且确实满足出生的要求，那么它就是0“-基本上，T处的LWSS表示元像素应该切换其当前状态。(T=T，如果像素当前是活的并且不满足生存要求，或者如果像素当前是死的并且确实满足出生的要求，那么它就是0)--基本上，T处的LWSS表示元像素应该切换其当前状态。

T处的LWSS遵循此处所示的路径。在6点28分，你可以看到LWSS在一系列曲折中导航时，变成了滑翔机，然后又回来了。在6：39，它发射一个向上倾斜的滑翔机，然后变成一个LWSS，然后到达同步缓冲区，最终到达信元状态船位(与C不同，下一段将详细介绍这一点)。最初的LWSS继续向左，分别在6：42和6：48拍摄另外两个滑翔机；每个滑翔机都会变成一个LWSS，一个指向图元的右下角，另一个指向图元的左上角，以切换输出显示的状态(更多信息将在下一节中介绍)。

单元状态船位实际上存储了单元的当前状态(C根据船位的状态定期更新)。如果存在船位，表示元像素的当前状态为“OFF”，则传入的LWSS将形成与其碰撞的滑翔机并将其移除(从7：03开始)。如果单元状态船位不存在，表明元像素的当前状态为“开”，则传入的LWSS将形成创建新船位的滑翔机(从18：58开始)。

最后，让我们跟随触发整个系列事件的原始LWSS的路径。它遵循这里所示的外部路径，被转换为MWSS并朝向单元状态船位。如果船位存在，它就会与之相撞而死亡，尽管它确实在这次死亡期间保存了船位(3：18)。如果没有船位，它就会毫发无损地驶过，继续向右行驶(7：14)。这与MWSS在细胞周围进行逆时针循环，在所有邻居的输入上触发蜜比特反应是相同的。该MWSS仅被允许在单元状态船位不存在的情况下、在元素为“开”的情况下进行循环。就在它离开去做环游之前，它发射了一架滑翔机，滑翔机在周围弹跳，最终在C(7：18)处放置了一艘船。在7点53分，你可以看到它引发了围绕元素的8个蜜位反应中的第一个，每个摩尔邻居一个。

元像素的最后一块是输出显示，它使用一吨重的宇宙飞船填充一个大的正方形区域，因此看起来或多或少是白色的。两个同步的LWSS切换输出显示；它们来自前面段落中描述的逻辑机制，如下所示。它们的计时通过路径上的一系列弯曲和滑翔机的变换来同步，然后它们被用来切换HWSS枪，从而触发一系列LWSS“突如其来”的反应。LWSS流填满了正方形空间，并在元素的中心相互湮灭，如下所示。这两个锁闩的机构相似：

如果你有兴趣了解更多，这里有一些相关的书籍和论文可供查阅：

威廉·庞德斯通(William Poundstone)的“递归的宇宙”(The Recursive宇宙，1985)--把这篇博客文章看作是对你阅读这本书的延伸恳求。从“生命”的介绍开始，逐步瓦解康威关于生命中存在自我复制模式的证明。

康威、贝里坎普和盖伊的“为你的数学剧赢得途径”(1982)--包括约翰·康威的“生活中存在自我复制模式的原始证据”(WINING WAYS YOUR MATHORIAL PLAYS，1982)。虽然这份证明没有列出这样一台机器的确切计划，但它证明了所有必要的部件都存在。几十年后，这些复制者的第一批实现开始出现在在线生活论坛上。

斯蒂芬·拉夫勒(Stephan Rfler)和莱尼亚(Lenia)合著的SmoothLife(2011)和Lenia(2019)。

.