康威生命游戏工坊

乌兰的一句话，诺依曼的一台机器 1940s–1966 · 元胞自动机的起点

生命游戏不是凭空出现的玩具，而是一个大问题的简化版。20 世纪 40 年代，冯·诺依曼（John von Neumann）想回答「机器能否复制自身」：在数学家乌兰（Stanisław Ulam）的建议下，他把空间离散成方格、把时间切成一代一代，用「元胞自动机」来构造这台机器。他在 1950 年代完成的自我复制机占了约 5 万个格子、需要 29 种状态，规则极其繁复（遗著《Theory of Self-Reproducing Automata》1966 年出版）。

结论很有分量：自我复制在逻辑上是可能的——只是代价高得难以直视。此后二十年，简化这套机器一直是元胞自动机研究的暗线。

十八个月的下午茶：康威怎样调制三条规则 1967–1970 · 剑桥

1960 年代末，剑桥的约翰·何顿·康威（John Horton Conway）决定把这个简化问题做成一种「纸笔玩具」：规则要简单到能用一张围棋盘和黑白棋子手工推演。最费事的正是「怎样才算好规则」。他先试过三状态版本——两种活细胞被朋友戏称为「女演员」与「主教」，配上一套苛刻的出生与配对规则；结果要么全部膨胀，要么全部死光，很难平衡。折腾约十八个月的下午茶之后，他回到二状态，终于定下三条（加德纳 1970 年专栏原文）：

• 存活：活细胞有 2 或 3 个活邻居，下一代继续活。
• 死亡：活细胞邻居 ≥ 4 死于拥挤；邻居 ≤ 1 死于孤独。
• 出生：空格恰有 3 个活邻居，下一代诞生新细胞。

康威选规则时有明确的三条设计准则（今称「康威三愿」）：① 没有任何初始图样能被简单证明会无限增长；② 却要存在看起来会无限增长的图样；③ 还要有简单图样能长期变化，最后以三种方式收场——灭绝、稳定、或进入周期振荡。一句话：让族群的命运不可预测。规则记作 B3/S23（Birth on 3, Survival on 2,3）。

最早的图样全部靠纸笔与围棋盘发现。康威检查各种小种子的归宿时注意到，五个细胞组成的 R-五连方（他记作 F-pentomino）迟迟不肯稳定：它要跑 1103 代，留下 116 个细胞和 六只逃逸的滑翔机——而那六只滑翔机，正是人类发现的第一批「空间船」。

1970 年 10 月：加德纳的专栏与五十美元悬赏 《科学美国人》223 卷 120–123 页

1970 年 10 月，科普圣手马丁·加德纳在《科学美国人》「数学游戏」专栏上写下标题：《约翰·康威新独玩游戏的奇妙组合》（The fantastic combinations of John Conway's new solitaire game "life"）。他写道：「因为它与生物社会的兴衰更替相像，它属于正在壮大的一类所谓『仿真游戏』。」这一期引发了该刊当时创纪录的读者来信，康威一夜成名。

专栏里挂出了康威的悬赏：五十美元，奖给能在 1970 年底前证明或推翻「不存在无限增长图样」这一猜想的人。加德纳还提示了两条可能的反例路线：能持续发射空间船的「枪」（gun），或边走边留下残骸的「喷气列车」（puffer train）。

1970 年 11 月：滑翔机枪与 MIT 的黑客们 悬赏被推翻 · 生命游戏走入计算机

奖金一个月后就被领走。MIT 的比尔·高斯帕（Bill Gosper）与五位同伴用计算机搜出了「滑翔机枪」——一台固定不动的装置，第 15 代射出第一只滑翔机，此后每 30 代再射一只。他们给加德纳发去一封电报，内容就是需要点亮的格点坐标。人口可以无限增长，至此成为定理级别的否定。生命游戏的第一件大事，就这样由一群「黑客」完成——1970 年还是计算机的洪荒时代，康威本人全程用围棋子和纸笔推演。

此后狂热蔓延：1971 年 3 月，罗伯特·温赖特（Robert Wainwright）编印了第一份生命游戏通讯《Lifeline》；喷气列车、发射空间船的「耙子」（rake）、留下枪的「饲养者」（breeder）陆续出现；1974 年《时代》周刊甚至抱怨「狂热信徒们可能已经浪费了价值数百万美元的宝贵机时」。

1971–1974：伊甸园与长寿者 从图样竞赛到定理

理论问题同样迅速推进。1963 年摩尔与迈希尔证明了一条漂亮定理：在生命游戏这类元胞自动机中，只要存在两个不同的有限图样演化为同一状态，就必然存在没有前驱的图样——所谓「伊甸园」，只能出现在第 0 代。生命游戏显然满足前提（全死与单格都演变为全死），所以伊甸园必然存在。1971 年，MIT 的罗杰·班克斯等人给出了第一个显式例子（33 × 9 的包围盒、226 格）；2004 年弗拉门坎普把规模压到 72 格，2011 年缩到 56 格；2016 年埃克找到高度仅 5 格的伊甸园（5 × 83），并证明高度不可能 ≤ 3。

另一条线是「小种子、长历史」的长寿者（methuselah，名字取自圣经里活了 969 岁的玛土撒拉）：R-五连方 1103 代后稳定为 116 格；橡实（acorn，7 格，Charles Corderman 设计）要 5206 代才长出 633 格的「橡树」，还甩出 13 只滑翔机；最短命的顽固分子（diehard）则恰好相反——活跃 130 代后彻底消失，至今被认为是「7 格以内最长灭绝」的记录保持者。

1982：从玩具到定理 《Winning Ways》里的图灵完备性证明

真正把生命游戏钉进数学史的是 1982 年。康威与贝尔坎普、盖伊合著的《Winning Ways for Your Mathematical Plays》末章给出证明：生命游戏包含一台通用计算机，也包含一台通用构造器（1980 年代初他与高斯帕各自完成了「通用化」的路径）。手法相当工程化：用枪产生的滑翔机流充当 0/1 信号，用「吞噬者」吸收信号，用滑块存储器（sliding block memory）存数据，把逻辑门与有限计算机的整套电路在棋盘上搭出来——最后让整台机器在程序停机时自毁，以此标志「计算结束」。

结论有锋利的一面：任何算法可计算的问题都能编码成生命游戏中的图样，于是「某个初始图样最终是否会彻底消失」是不可判定的。此后人们干脆把机器真的搭出来：2000 年保罗·伦德尔（Paul Rendell）直接实现了图灵机；2002 年查普曼用 Minsky 寄存器机造出有限通用计算机；2009 年古彻造出 Spartan 通用构造器；2010–2011 年伦德尔的通用图灵机完成；2016 年鲁瓦佐搭出八位可编程计算机，2021 年又做了可扩展版。

算法与软件：HashLife、Golly 与 LifeWiki 1980s–2015 · 从单机到众包

要让巨型图样跑起来，光有规则不够。1980 年代初，高斯帕提出 HashLife：把棋盘切成四叉树并缓存「同一区域若干代后的结果」，让重复结构被反复复用，速度提升可达天文数字级。1989 年迪安·希克森写出第一个振荡子搜索程序，从此「发现」开始交给机器；1990 年代的 Life32 与 Java 程序让爱好者把图样库搬上互联网。

2005 年 7 月，Golly 问世（Trevorrow 与 Rokicki 开发），它把 HashLife 与无限棋盘一起交到玩家手里，2006 年布鲁斯·杜依的 OTCA 元胞正好用来展示它的威力。2009 年 1 月 LifeWiki 上线，图样有了统一命名与档案；2015 年古彻推出 Catagolue 在线数据库，配合众包搜索程序 apgsearch，把「随机汤里又冒出什么新东西」变成了每天由全世界机器共同完成的日常工作。

自我复制与斜行船：Gemini 与 Sir Robin 2010–2018 · 补完最后两块拼图

此后近三十年，人类已知的空间船只能沿正交或对角方向直行，直到 2010 年 5 月 18 日，安德鲁·韦德公布 Gemini：第一艘斜行空间船，也是第一艘真正「自我复制」的船——它带着一条由滑翔机编码的指令带，一边前进一边复制自己并销毁母体，位移 (5, 1)，复制一轮要三千多万代。2013 年 11 月，戴夫·格林造出第一个能完整复制自身（含指令带）的复制器；2018 年 10 月，古彻完成 0E0P 元胞——一种可以自我复制的「元胞中的元胞」。

与此并行的是「基本」空间船的进展。贝尔坎普 1982 年就预言过「像国际象棋骑士那样走」的船存在，但一直无人找到。2018 年 3 月，古彻与罗基茨发现了 Sir Robin：第一艘基本斜行（骑士）船，每 6 代位移 (2, 1)——这是 48 年来基本空间船运动方式的第一位新成员。两年后的 2020 年 4 月 11 日，康威因新冠肺炎在新泽西去世，享年 82 岁；他生前把生命游戏称作「零玩家游戏」——摆好棋盘以后，游戏便不再需要任何人。

仍在生长的 2020 年代 2022 教科书 · 2023 全能周期定理

康威走了，生命游戏没有停。2022 年，约翰斯顿与格林的教科书《Conway's Game of Life: Mathematics and Construction》出版，半个世纪的技巧第一次被系统整理；同年，悬置五十年的「唯一父亲问题」被萨洛与特尔迈解决（造出第一个不可合成的静物），坎宁安造出第一个不可合成的振荡子。2023 年 6 月，韦德证明不存在「高度 4 的孤儿」；2023 年 7 月，生命游戏被证明是 omniperiodic——每一种周期都存在振荡子。

作为一个「玩具」，它喂养出了两门学问：以它为核心的人工生命（Artificial Life）研究，以及沃尔弗拉姆在《一种新科学》里称为「第四类」的复杂行为——既不彻底随机、也不彻底重复。丹尼特曾长期用它向读者解释「没有设计者的设计」如何可能。而在编程世界里，它几乎是每个人写下的第一个「会自己动」的程序。

本工坊想请你亲手体会的，正是它起点的那个瞬间：三条规则，一片宇宙。若想从更小的形状入门（三连方、五连方各自的归宿），可移步本站《方块生命体 · 生命形状实验室》；那里问的正是康威当年问的问题——它们会怎样移动？

年份	事件
1940s–1966	冯·诺依曼在乌兰建议下构造元胞自动机自我复制机（29 状态），遗著 1966 年出版
1967–1970	康威在剑桥经约十八个月的纸笔实验定下 B3/S23；发现静物、振荡子、滑翔机与 R-五连方的长寿
1970.10	加德纳《科学美国人》专栏《康威新独玩游戏的奇妙组合》发表，生命游戏走向大众；悬赏 50 美元
1970.11	MIT 高斯帕团队发现滑翔机枪（每 30 代射出一只滑翔机），赢得悬赏，推翻「无无限增长」猜想
1971	《Lifeline》通讯创刊；班克斯等给出第一个显式伊甸园（33 × 9）
1974	《时代》周刊报道生命游戏狂热「浪费数百万美元机时」
1980s 初	高斯帕提出 HashLife 算法，巨图样演化速度提升多个数量级
1982	康威在《Winning Ways》中证明生命游戏含通用计算机与通用构造器 → 图灵完备
1989	希克森写出第一个振荡子搜索程序；XLife 让大图样在普通机器上可算
2000–2011	伦德尔实现图灵机（2000）并完成通用图灵机（2010–2011）；查普曼的有限通用计算机（2002）
2004	「毛虫」（Caterpillar）完成——第一艘自持巨型空间船
2005–2009	Golly 发布（2005.7）；OTCA 元胞（2006）；论坛（2008）；LifeWiki 上线（2009.1）
2010	Gemini：第一艘斜行、自我复制的空间船（韦德，5 月 18 日）
2013–2015	首个完整自我复制器（格林，2013）；Catagolue 在线数据库与众包搜索上线（2015）；辛普金滑翔机枪（2015）
2016	铜头蛇（c/10 小船）与「意大利面怪物」（3c/7）等新速度空间船；埃克发现高度 5 的伊甸园
2018	Sir Robin：第一艘基本骑士船（每 6 代位移 (2,1)）；0E0P 元胞完成
2020.4.11	康威因新冠肺炎逝世，享年 82 岁
2022	约翰斯顿与格林的教科书出版；「唯一父亲问题」解决，首个不可合成静物与振荡子问世
2023	生命游戏被证明为 omniperiodic（每种周期的振荡子都存在）；高度 4 孤儿不存在得证