数学的“生命游戏”揭示了长期寻找的重复模式广达杂志

1969 年，英国数学家约翰·康威设计了一套极其简单的规则来创建复杂的行为。他的生命游戏，通常简称为生命，在无限的方形细胞网格上展开。每个细胞都可以是“活的”或“死的”。网格经过一系列轮次（或“世代”）的演变，每个单元的命运由其周围的八个单元决定。规则如下：

1. 诞生：一个死亡的细胞，恰好有三个活着的邻居，就会变得活着。
2. 生存：具有两个或三个邻居的活细胞保持存活。
3. 死亡：一个活细胞的邻居数量少于两个或多于三个的就会死亡。

这些简单的规则创建了令人惊讶的多样化模式或“生命形式”，它们是从网格的许多不同可能的起始配置演变而来的。游戏爱好者已经在不断扩大的范围内对这些模式进行了统计和分类。 在线目录。康威发现了一种称为信号灯的模式，它在两种状态之间振荡。

第二年，他发现了一种更为复杂的模式，称为脉冲星，它在三种不同的状态之间振荡。

振荡子被发现后不久，游戏的早期探索者就想知道是否存在每个周期的振荡子。 “一开始，我们只看到了周期 1、2、3、4 和 15，”计算机程序员兼数学家 Bill Gosper 说道，他在接下来的几十年里发现了 17 种不同的新型振荡器。令人惊讶的是，15 周期振荡器（如下所示）在随机搜索中频繁出现。

对于那些愿意寻找它们的人来说，惊喜潜藏着。 “从数小时和数天的观看来看，第五阶段似乎是不可能的，”高斯珀说。 5 年，即该游戏发明两年后，一款游戏被发现。随着计算机技术的出现，寻找新的振荡器成为了游戏的一个主要焦点。在办公室电脑上进行的秘密搜查的记录已成为该游戏民间传说的基石。 “从企业和大学大型机中窃取的计算机时间数量令人震惊，”高斯珀说。

整个 1970 世纪 15 年代，数学家和爱好者填补了其他较短的周期，并发现了一些较长的周期。最终，数学家发现了一种构建长周期振荡器的系统方法。但事实证明，周期在 43 到 XNUMX 之间的振荡器很难找到。 “多年来人们一直在试图找出中间点，”说 玛雅·卡尔波维奇，马里兰大学研究生。填补空白迫使研究人员想出一系列新技术，突破元胞自动机的界限，数学家将元胞自动机称为“不断演化的网格”，如“生命”。

现在，卡尔波维奇和六位合著者在一份声明中宣布 十二月预印本 他们发现了最后两个缺失的周期：19 和 41。随着这些间隙的填补，生命现在被认为是“全周期的”——说出一个正整数，并且存在一个在这么多步骤之后重复自身的模式。

致力于研究生命的新兴社区包括许多研究数学家和许多业余爱好者，他们不仅发现了振荡器，还发现了各种新模式。他们发现了穿越网格的模式，称为宇宙飞船，以及构建其他模式的模式：枪支、构造者和繁殖者。他们发现了计算素数的模式，甚至可以执行任意复杂算法的模式。

周期短于 15 的振荡器可以手动找到，也可以使用一次搜索一个单元的基本算法来找到。但随着周期变长，复杂性也随之增加，使得暴力搜索的效率大大降低。 “对于小周期，你可以直接搜索，”31 年发现第一个 2010 周期振荡器的新论文合著者 Matthias Merzenich 说。“但你不能真正超越这个范围。你不能只选择一个时期并搜索它。” （梅泽尼奇于 2021 年获得俄勒冈州立大学数学博士学位，但目前在农场工作。）

1996 年，加拿大自由计算机顾问兼生活爱好者 David Buckingham（自 1970 世纪 61 年代末以来一直在寻找模式）表明，通过以无限循环方式围绕闭合轨道发送模式，可以构造周期 61 及更高周期的振荡器。通过控制循环的长度——以及模式完成一次往返所需的时间——白金汉发现他可以让周期变得尽可能大。 “这是化学反应，没有奇怪的气味或破碎的玻璃器皿，”他说。 “就像建造化合物，然后探索它们之间的相互作用。”这意味着，他一下子就想出了一种构造任意长周期振荡器的方法，只要它们长于 XNUMX 即可。

1990 世纪 15 年代中期出现了大量结果，通过对已知振荡器的创造性组合发现了许多 61 至 XNUMX 之间缺失的振荡器，这些振荡器被赋予了一系列丰富多彩的名称。餐饮者与红绿灯结合在一起，火山喷出火花，食客吃着滑翔机。

到了21世纪之交，只​​有十几个时期仍然杰出。 “解决这个问题似乎很有可能，”梅泽尼奇说。 2013 年，一项名为“Snark 环”的新发现改进了 Buckingham 1996 年的技术，并将截止值降低到可以轻松构建振荡器的范围，从 61 降低到 43。这样只留下了 2019 个缺失周期。 2022 年又发现了一颗，19 年又发现了两颗，只剩下 41 颗和 XNUMX 颗——都是素数。 “素数更难，因为你不能使用小周期振荡器来构造它们，”梅泽尼奇说。

纽约大学阿布扎比分校的博士后研究员、这篇新论文的另一位合著者米切尔·赖利 (Mitchell Riley) 长期以来一直对一种称为扰动器的振荡器很感兴趣。 “麻烦者的工作方式是，中间有一个活跃的模式，而外部有一些稳定的东西与之反应，”莱利解释道。这种稳定的物质，称为催化剂，可以将活性模式推回其原始状态。

设计它们很困难。 “所有这些模式都极其脆弱，”莱利说。 “如果你把一个点放错了位置，它们通常就会爆炸。”

莱利创建了一个名为“律师”的计划来寻找新的催化剂。 “我们正在寻找的是坚固的静物画。重点是我们希望他们能够与中间发生的事情互动，然后恢复，”莱利说。

莱利将巴里斯特发现的催化剂输入到另一个搜索程序中，将它们与活跃模式配对。他说，这主要导致了失败。 “其中一种催化剂在相互作用中幸存下来的情况相当罕见。没有成功的保证。你只是祈祷自己能中大奖。感觉有点像赌博。”

最终，他的赌注得到了回报。在经历了几次险些失败之后，以及对代码进行了修改，将搜索范围扩大到包括对称模式之后，他发现了一种可以维持 19 周期振荡器的催化剂相互作用。赖利说：“人们一直在尝试各种非常复杂的搜索，其中有很多催化剂和中间有很多稀有的活性物质，但所需要的只是找到这种新的厚实催化剂。”

最后一个缺失的句号 41 是由另一位合著者 Nicolo Brown 发现的，他目前还是加州大学圣克鲁斯分校数学专业的本科生。布朗使用滑翔机作为催化剂，这是梅泽尼奇首先提出的想法。

“在过去的十年里，我们发现了如此多的深层行为，”卡尔波维奇说。 “每个人都在庆祝一周——然后就开始做其他事情。还有很多其他问题需要解决。”给定周期的振荡器可以做得更小吗？能否找到每个细胞都振荡的振荡器？特定时期可以制造枪吗？可以让宇宙飞船以特定的速度行驶吗？

正如白金汉所说，“这就像一个孩子在一个无限的玩具店里。”