百里路 / 数学 · 计算 · 复杂系统
№ 072
LESSON 072 · COMPUTATION
元胞自动机与生命游戏
Cellular Automata & Conway's Game of Life · 三行规则，和一个原则上没有捷径的未来
- 提出者
- 冯·诺依曼 / 乌拉姆 / 康威
- 年份
- 1948 / 1970
- 领域
- 数学 · 计算 · 复杂系统
- 核心命题
- 确定，但没有捷径
一
缘起 · 机器能不能造出和自己一样复杂的机器
ORIGIN
1948 年，约翰·冯·诺依曼在加州理工的一次会议上提出了一个几乎不像数学的问题：一台机器能不能造出一台和它自己一样复杂的机器？
直觉说不能。机器要造别的机器，总得损耗点什么——工具比产物精密，模具比零件复杂，一代不如一代。可生命显然做到了：细胞造细胞，几十亿年没有退化。那么"自我复制"到底需要什么最小的逻辑结构？
问题的难点在于载体。冯·诺依曼一开始想的是一台漂在零件湖上的机器人，伸出机械臂捡零件装自己——这个模型太脏，物理细节淹没了逻辑。是同在洛斯阿拉莫斯的斯坦尼斯瓦夫·乌拉姆给了他那个决定性的建议：把物理扔掉，改用一张无限大的方格纸。
每个格子只有有限几种状态；每个格子只看得见自己的邻居；所有格子按同一条规则、在同一个时钟节拍上一起更新。就这样。元胞自动机（cellular automaton）诞生了——一个连空间、时间、物质都被离散成格子的世界。
冯·诺依曼在这张纸上造出了一台 29 种状态、约二十万个格子的通用构造器，并证明了它可以复制自己。他没写完这项工作就在 1957 年去世，手稿由阿瑟·伯克斯整理，1966 年才以《自我复制自动机理论》出版。
此后二十年，元胞自动机基本上是少数几个数学家的玩具。真正把它变成一件全世界都在玩的东西的，是 1970 年 10 月的一期《科学美国人》——马丁·加德纳在他的"数学游戏"专栏里，介绍了剑桥数学家约翰·康威刚发明的一个只有三条规则的棋盘游戏。
康威想找的是一条最简单的规则，
简单到看一眼就懂，却又复杂到你没法预言它会长成什么样。
他找到了。此后五十余年，这个叫"生命游戏"的东西被证明可以计算任何可计算的东西，可以自我复制，可以在里面用生命游戏模拟生命游戏——而与此同时，关于它的一些最简单的问题被证明原则上无法回答。本篇讲的正是这后半句。
二
原典 · 三条规则
THE PRIMARY TEXT
CONWAY / GARDNER, 1970 · 生命游戏
无限大的方格纸，每个格子只有两种状态：活或死。每个格子有八个邻居。所有格子同时按下面三条更新：
一、孤独。活格子若活邻居少于两个，下一步死。
二、拥挤。活格子若活邻居多于三个，下一步死。
三、繁衍。活格子有两个或三个活邻居则继续活；死格子恰好有三个活邻居则复活。
没有别的规则。没有随机数，没有玩家，没有目标。初始图样一旦摆好，此后每一步都被完全决定。
Martin Gardner《Mathematical Games: The fantastic combinations of John Conway's new solitaire game "life"》Scientific American 223 (October 1970), pp.120–123。规则今天通常记作 B3/S23：三个邻居则出生，两三个邻居则存活。
而在这个玩具背后，是冯·诺依曼二十年前用同一种格子世界给出的、关于自我复制的那个答案。它比生命游戏抽象得多，也重要得多：
VON NEUMANN, 1948–1953 · 自我复制需要什么
一台能复制自己的机器，必须包含一份关于它自己的描述。而这份描述必须被使用两次，且用法完全不同：
第一次当作指令——照着它造出一台新机器；
第二次当作数据——原封不动地抄一份，塞进新机器里。
缺了第一次，你造不出东西；缺了第二次，你造出的那台不会再复制。自我复制的最小结构，就是"一份既被执行、又被复制的描述"。
John von Neumann《Theory of Self-Reproducing Automata》(Arthur W. Burks 编，University of Illinois Press, 1966)。上为核心论证的转述。冯·诺依曼给出这套逻辑时，DNA 的双螺旋结构尚未公布（1953）——但请注意，这个对应是后人回头看出来的，他本人谈的是自动机，不是遗传学。
三行规则和一份被用两次的描述——本篇要讲的全部东西，都从这两块石头上长出来。
三
释义 · 你可以完美复现它，却仍然预言不了它
PLAIN MEANING
元胞自动机是这个世界上最"干净"的一类系统。它没有随机性，没有测量误差，没有隐藏变量，甚至没有实数——全部是整数格子。你把同一个初始图样输进去跑一万遍，会得到一万次一模一样的结果。
可就是这样的系统，你没有办法预言它一百万步之后长什么样。
请务必把这里的"不可预测"与混沌区分开。这是本篇最要紧的一次校准：
混沌（№048）的不可预测来自误差被放大：初始条件差之毫厘，指数发散，而你永远测不准初始条件。它是连续系统的病。
元胞自动机的不可预测完全不是这么回事。这里没有误差可放大——初始状态是几个格子亮着，你知道得一清二楚。它的麻烦是另一种：要知道第 n 步的样子，你必须一步一步跑完那 n 步，没有任何公式能让你跳过去。
沃尔弗拉姆给这件事起了个名字：计算不可约性（computational irreducibility）。
可以拿两个东西对照着体会。抛出去的石头，你不需要一秒一秒地模拟它的飞行——一个抛物线公式就能直接告诉你三秒后它在哪，这叫可约：自然界的行为可以被压缩成一条比它本身短得多的算法。而一个足够复杂的元胞自动机不给你这个便利，要看结果，只能让它跑；它自己就是关于自己最短的那份描述。
这不是"我们还不够聪明"。
这是：那条捷径不存在。
更狠的一层在后面。生命游戏被证明可以模拟图灵机——也就是说，它能计算任何计算机能计算的东西。而只要一个系统达到这个门槛，关于它未来的一般性问题就立刻掉进图灵 1936 年划下的那道深渊：这些问题是不可判定的，不存在任何算法，能对任意给定的图样，判断它是否最终会消失。
于是有了这个奇特的组合：一个三行规则写完、任何人五分钟就能实现的玩具，其中藏着与哥德尔、图灵同一个级别的边界（见连接卡 №040）。而这条边界不是关于"很难算"，是关于"没有办法"。
四
后人之论
LATER INTERPRETATIONS
五
案例
CASE STUDIES
CASE 01
1948–1966 · 洛斯阿拉莫斯
先算出生命必须怎么做，再去看它是不是这么做的
冯·诺依曼的通用构造器有 29 种状态、约二十万个格子，是那张方格纸上一台庞大得吓人的机器。但它真正的产出不是那台机器，是那条逻辑：自我复制需要一份被使用两次的描述——一次当指令执行，一次当数据抄写。
他给出这个结论的时间，早于沃森与克里克 1953 年公布 DNA 双螺旋结构。而后来我们知道，细胞干的正是这两件事：DNA 被转录翻译成蛋白质（当指令用），又被复制成一份新的 DNA（当数据用）。
但请不要把这说成"冯·诺依曼预言了 DNA"——他谈的是自动机的逻辑，与遗传学没有直接来往，这个对应是后人回头看出来的。
启示：这是"纯逻辑先于经验发现"的一个罕见样本。当一件事的约束足够硬，你有时可以在看见它之前，先算出它必须长什么样。代价是：这类推演对"实际用了哪种分子"完全沉默——它给出的是必要结构，不是实现方案。
CASE 02
1970-11-04 · 麻省理工
五十美元，和那把每三十步射出一只滑翔机的枪
加德纳的专栏登出后，康威悬赏 50 美元，征求一个答案：存不存在一个有限的初始图样，能让活格子的数量无限增长？康威自己猜是不存在。
一个月后，1970 年 11 月 4 日，MIT 人工智能实验室的比尔·戈斯珀和他的同伴找到了它——一个 36 个活格子的图样，每 30 步吐出一只"滑翔机"（一个会斜着爬行的小图样），永远吐下去。这就是戈斯珀滑翔机枪。康威输了赌，付了钱。
而这件事的分量远超一个赌局：有了枪，就有了信号源。能持续发射滑翔机，就能让滑翔机流相互碰撞；能让它们碰撞，就能做出与门、非门、存储——一条通往"在生命游戏里造计算机"的路，从这一天开始铺。
启示：发明规则的人，对自己规则的后果猜错了，而且是在一个月内被证伪的。这几乎是本篇的主题句：即使你亲手写下了全部规则，你依然不知道它们能干什么。规则的作者并不比别人拥有更多的预言权——他只有和别人一样的一条路：跑一遍看看。
CASE 03
1998–2004 · 规则 110
通用计算的门槛，低得吓人
请先感受一下规则 110 有多简陋：一维的一排格子，每格非黑即白，每格只看自己和左右两个邻居，一共八种输入情形，每种对应一个输出。整条规则可以写在一张便签上。
库克证明了：这样一条规则，在合适的背景图样上，可以模拟任意图灵机——也就是说，它能计算任何你的电脑能计算的东西。理论上，你可以用它跑操作系统。
这个结果支持了沃尔弗拉姆的一个观察：通用计算不是稀有的、需要精心设计才能达到的高级性质，而是几乎"随手就撞上"的东西。在 256 条最简单的规则里就已经有它。
启示：这一条同时给出了正反两面。正面：复杂到无法预测，并不需要复杂的原因——最简陋的规则就够了。反面（见反例④）：既然通用计算这么容易达到，那么"某系统是图灵完备的"这句话，几乎不携带任何关于它实际行为的信息——它是一条极低的门槛，不是一枚勋章。
CASE 04
2000 / 2010 · 生命游戏中的图灵机与自我复制
在方格纸上，把冯·诺依曼的问题原样答了一遍
2000 年，保罗·伦德尔在生命游戏里造出了一台可运行的图灵机；2010 年他完成了通用版本，并写成博士论文，2015 年由施普林格出书。
2010 年 5 月，安德鲁·韦德公布了名为 Gemini 的图样：它一边把自己拆掉，一边在斜前方造出一个完整的自己，周期约三千四百万步。它的做法与冯·诺依曼六十年前算出来的逻辑一模一样——一条由滑翔机组成的指令带，既被执行，又被复制。
再往后，人们在生命游戏里造出了运行着生命游戏的元胞（OTCA metapixel）：你可以缩小看一眼——里面还是同一个游戏。
启示：三条规则里装得下图灵机、自我复制、以及它自己。"简单"与"能力"之间没有必然联系，而我们的直觉几乎总是把这两件事绑在一起。下次判断"这个机制太简单了，不可能产生那种行为"，请先想一想 B3/S23。
CASE 05
2019 · 规则 30 的三万美元
三行规则产出的序列，我们至今证明不了它是不是随机的
规则 30 是另一条同样简陋的一维规则。从单独一个黑格子出发，它长出的图样看起来完全没有规律——沃尔弗拉姆早年甚至把它中间那一列直接拿来当 Mathematica 的随机数发生器。
2019 年，他为规则 30 的三个问题各悬赏 1 万美元，共 3 万美元：中间那一列是否永远不周期？黑白出现的频率是否长期各占一半？计算第 n 个格子是否必须付出至少与 n 同量级的代价？
三个问题至今没有一个被解决。
启示：这是把"确定"与"可预测"切开得最干净的一刀。规则 30 是完全确定的：给我初始行，我能算出任何一格，绝无歧义。可我们连"它的中间一列会不会重复"这样一个小学生能听懂的问题都答不上来。确定性给你的是复现能力，从来不是预言能力。
六
反例与限制
CRITIQUE & LIMITS
元胞自动机本身是数学对象，它的定理不会错。会错的是围绕它长出来的那一大圈主张——关于宇宙、关于复杂性、关于"这就是万物的解释"。这一节写的是那一圈。
-
① 最大的那个主张缺少可检验的预言。沃尔弗拉姆《一种新科学》的野心不止于数学：他主张宇宙本身可能就是一个简单程序在跑。问题是，这个主张没有给出任何可被实验分辨的预测。批评最锋利的一处来自计算机科学家斯科特·阿伦森 2002 年的书评：他证明了书中那套"用长程线连接纠缠粒子"的确定性隐变量图景，无法同时兼容狭义相对论与已被实验反复确认的贝尔不等式违反——要么破坏洛伦兹不变性，要么与量子力学冲突，或者两者兼有。"世界可能是个程序"是一个漂亮的隐喻；把隐喻当成物理理论则是另一回事。
-
② "计算不可约性"很难被证伪。这个概念极有启发，但在实践中它几乎总是以否定形式出现："这个系统没有捷径。"而对于绝大多数具体系统，"不存在更短的算法"从未被证明，只是"还没有人找到"。历史上大量看似不可约的现象后来被找到了公式。因此严谨的用法是把它当成一个默认预期（复杂系统通常没有捷径，别一上来就找公式），而不是当成一个已被证明的判决。
-
③ 模拟得像，不等于机制对。元胞自动机能重现的东西多得惊人：交通拥堵、雪花、贝壳花纹、林火蔓延、城市扩张、种群消长。但能重现现象，与找对了机制，是两件事——同一个宏观图样常常可以由很多套完全不同的规则产生（多重实现）。看到模型跑出了和真实数据相似的曲线就宣布"于是它是这样运作的"，是复杂系统研究里最常见的一次滑坡，也是 №041 涌现那一篇踩过的同一个坑。拟合力强，恰恰意味着证伪力弱。
-
④ "图灵完备"是一条极低的门槛，不是一枚勋章。规则 110 通用、生命游戏通用、Excel 公式通用、《我的世界》红石通用、乃至一堆本来不该通用的东西都被证明通用——几乎任何允许条件与循环的系统，稍加折腾就能达到这个标准。因此"某某是图灵完备的"这句话给出的信息量，接近于"某某是非平凡的"。把它当作深刻性的证书，是外行最常见的一次误用；而它真正的用处是反向的——一旦某物图灵完备，你就知道关于它的一般性问题不可判定，即：不要再去找那个通用的判断算法了。
-
⑤ 别把"没有捷径"读成"所以无法管理"。不可约性说的是"无法用比运行更短的方式精确算出全部细节"，它不排除粗粒度的统计规律、可靠的边界条件、有效的干预。生命游戏里没有预测某个图样命运的通用算法，但仍然有一大堆被严格证明的局部结论（哪些图样一定稳定、哪些结构可以做出什么）。把"不可预测"当成"怎么做都行"的许可证，是从一条数学结论跳到一句处世态度——中间那一步是偷的。
正确姿势：把它当一副追问"这件事有没有捷径"的眼镜。有捷径的，去找公式；没有捷径的，别再推演，去跑、去试、去做小规模的真实验。而这两类事情的分界，往往比"它看起来有多复杂"更值得先花力气判断。
七
相关理论
CONNECTIONS
混沌理论№048 Chaos Theory
⚠ 最该切开的对照
两者常被混为一谈，而它们的不可预测来源完全不同。
№048 是
误差被指数放大（连续系统，测不准初值）；元胞自动机
没有误差可放大，跑一万次结果相同，麻烦在于
没有比运行更短的路。一个是"算不准"，一个是"没捷径"。
涌现№041 Emergence
↔ 姊妹，但看的是两件事
№041 问"宏观新性质怎么从微观长出来"；本篇问"就算你完全知道微观规则，你能不能提前算出宏观结果"。
涌现讲生成，不可约性讲预测的边界。生命游戏是两篇共用的实验台。
停机问题Turing 1936 · Halting Problem
⟸ 直接上游
本篇最硬的那条结论完全是它的推论：一旦系统能模拟图灵机，"给定图样是否最终消失"就与"给定程序是否停机"同构，因而不可判定。不是难，是没有算法。
哥德尔不完备定理№040 Incompleteness
⟸ 同族边界
№040 划的是"证明"的边界，本篇划的是"预测"的边界，两者共享同一个形状：
系统一旦强到能谈论自己，就会长出自己回答不了的问题。而这两道墙都不是能力不足，是结构本身。
自我复制与冯·诺依曼探针Self-Replication
⟹ 直系产物
"一份既被执行又被复制的描述"这条结构，后来在 DNA、计算机病毒、编译器自举、乃至自我复制探针的设想里反复出现。它是本篇唯一一条可以直接搬到现实、且已被现实反复兑现的结论。
人工生命与混沌边缘Artificial Life · Langton
⟹ 后裔学科
1987 年从洛斯阿拉莫斯长出来的一整个领域：不研究"生命是什么做的"，研究"生命的逻辑可以由什么做出来"。最有趣的行为都挤在有序与混沌之间那条窄带上。
自组织临界Per Bak 1987 · Sandpile
↔ 平行模型
同样是格子上的简单局部规则，同样自发跑到临界状态，产出大小不一的雪崩与幂律分布（见
№016）。
沙堆模型与生命游戏是同一种研究策略的两个方向：用最贫瘠的规则去解释最常见的分布。
香农熵与柯氏复杂度№010 Shannon Entropy
↔ 度量工具
"这段输出到底是不是随机的""它能不能被压缩得更短"——回答这些问题要用
№010 那套语言。
计算不可约性说的正是：这个系统的历史，压缩不到比它自己更短。
八
致用
APPLICATION
以下五条里，第一、四条是从这套数学直接推出的；第二、三、五条是判断习惯与类比，请按类比看待。
-
先判断有没有捷径
面对一件要预测的事，先做分类：它是抛物线，还是生命游戏？有闭式解的（利息、载重、排期算术）去找公式，别用模拟；没有捷径的（一次产品发布、一场组织变革、一个社区的走向）就别再在会议室里往下推演第五步了——推演的成本会超过直接试一次。把力气从"预测它"改成"低成本地跑一遍"：原型、试点、灰度、A/B。在不可约的系统里，运行比推理便宜。
-
设计规则，不要设计结果
三行规则能长出图灵机，说明丰富的行为不需要丰富的规则。做团队制度、社区公约、平台机制时，与其穷举场景写成三十条细则（细则永远漏），不如定少数几条清晰、局部、人人能记住的规则，让复杂性自己长出来。但要接上反例⑤的另一半：规则少不等于放手不管——你写下的每一条局部规则，都会在你看不见的地方产生你没打算要的结构。
-
警惕"我的模型跑对了"
当一个模型（不管是元胞自动机、系统动力学还是回归）重现了真实数据，先别宣布懂了。问两句：有没有别的机制也能产生同样的曲线？这个模型给出了什么它不必然给出的预测？只会拟合已发生之事的模型，解释力再强也没有证伪力——它更像一幅画，不像一台仪器。
-
认出"这里没有通用判断法"
这一条有严格的数学依据。凡是被证明不可判定的问题，就不要再投人力去找那个万能的自动判断器——不存在能判定任意程序是否死循环的分析器，也不存在能判定任意规则集是否会产生冲突的检查器。正确的动作是退一步：接受一个保守而可靠、或宽松而漏报的近似，并明确写下它会在哪些情形下失效。知道墙在哪里，本身就省下了一支团队的年度预算。
-
对自己的规则保持谦逊
康威对自己发明的游戏猜错了，一个月后被人拿五十美元赌注证伪。你是某件事的规则制定者，并不给你关于它后果的额外预言权。因此：新规则上线后要留观察窗口、留可回滚的余地、留"我们可能猜错了"的公开承认空间。最危险的规则制定者，是那个相信自己已经想清楚了全部后果的人。
九
反观三问
THREE QUESTIONS
我手上正在反复推演的那件事，究竟是"还没算清楚"，还是根本没有捷径、只能跑一遍？我已经在推演上花了多久？
我定过的规则（团队的、家里的、自己的），有哪一条长出了我完全没预料到的结构——我当时凭什么以为自己预料得到？
我最近一次说"这么简单的东西不可能造成那么大的后果"，如果换成三行规则的生命游戏，这句话还站得住吗？
十
延伸阅读
FURTHER READING
-
Martin Gardner《Mathematical Games: The fantastic combinations of John Conway's new solitaire game "life"》
Scientific American 223, October 1970, pp.120–123 — 生命游戏第一次公开露面，三页专栏点燃了此后五十年
-
John von Neumann《Theory of Self-Reproducing Automata》(A. W. Burks 编)
University of Illinois Press, 1966 — 未完成的遗稿；"一份被使用两次的描述"出自此书
-
Stephen Wolfram《Universality and complexity in cellular automata》
Physica D 10, 1984, pp.1–35 — 四类行为的分类，一维元胞自动机研究的起点
-
Matthew Cook《Universality in Elementary Cellular Automata》
Complex Systems 15(1), 2004, pp.1–40 — 规则 110 图灵完备的证明；被压了六年才发表（见后人之论第四家）
-
Stephen Wolfram《A New Kind of Science》
Wolfram Media, 2002 — 1200 页的大书；计算不可约性与计算等价原理的出处，请连着下一条一起读
-
Scott Aaronson《Book Review: A New Kind of Science》
arXiv:quant-ph/0206089, 2002 — 本篇最推荐的批评文献；用贝尔不等式正面拆掉书中的物理主张
-
E. Berlekamp, J. Conway & R. Guy《Winning Ways for Your Mathematical Plays》
Academic Press, 1982 — 康威本人参与的那本；书中给出生命游戏可模拟计算的构造思路
-
维基百科：Conway's Game of Life
en.wikipedia.org/wiki/Conway's_Game_of_Life — 滑翔机枪、图灵机、自我复制图样的完整索引
乌拉姆在洛斯阿拉莫斯做的是另一件出名的事——蒙特卡洛方法。但他对本篇的贡献只有一句建议：不要造机器人，用格子。
这句建议的分量常被低估。它做的是一次彻底的抽象：把"自我复制"这个看起来充满物理、化学、生物细节的问题，剥成一个纯粹的组合逻辑问题——只剩下状态、邻居和更新规则。
此后半个多世纪，几乎所有关于复杂性的计算实验都住在乌拉姆这张方格纸上。找到一个足够贫瘠的模型，往往比找到一个足够丰富的模型更难，也更有用。
八十年代初，沃尔弗拉姆做了一件笨办法的事：把一维、两状态、只看左中右三格的元胞自动机——总共只有 256 条可能的规则——一条一条全部跑出来看。
他发现它们的行为整齐地落进四类：第一类归于一片死寂；第二类落进简单周期或稳定图样；第三类产出看起来完全随机的花纹；第四类最诡异——既不重复也不随机，长出一些局域的结构，互相碰撞、湮灭、传播。生命游戏就属于第四类。
由此他提出了两个更大的主张：计算不可约性（有些系统的演化没有捷径），和计算等价原理（几乎所有行为不平凡的系统，计算能力都是等价的——都能达到通用计算）。2002 年，他把这些写进一本 1200 页的《一种新科学》。
第一个主张今天被广泛接受为一个重要洞见；第二个主张更像哲学命题而非定理，而整本书遭到的批评见第六节。
朗顿想给沃尔弗拉姆那四类行为找一个可以拧的旋钮。他定义了一个极简单的参数 λ：在一条规则的全部条目里，输出为"活"的比例。
把 λ 从 0 慢慢调到 1，系统的行为会依次走过：死寂 → 周期 → 某个狭窄的过渡带 → 混沌。而最有意思的东西——那些能传递信息、能做计算的第四类结构——恰好挤在中间那条窄带上。朗顿称之为混沌边缘（edge of chaos）。
他还是人工生命（Artificial Life）这个领域的创立者：1987 年 9 月在洛斯阿拉莫斯组织了第一届人工生命研讨会，把"用计算重造生命的逻辑"变成一门正式学问。
诚实注明：λ 与"混沌边缘"作为定性图景很有启发，但作为定量判据一直有争议——同一个 λ 值可以对应差别极大的行为，后续研究普遍认为它是一个粗糙的指标而非精确的相变参数。
沃尔弗拉姆 1985 年猜测：256 条一维规则里的规则 110——一条只看左中右三格、写下来不到一行的规则——已经是图灵完备的。
九十年代，在沃尔弗拉姆手下做研究助理的库克把这个猜想证明了。这是一个惊人的结果：通用计算的门槛，比所有人以为的低得多。
然后事情变得不像数学史。1998 年库克在圣塔菲研究所的 CA98 会议上讲了这个证明，沃尔弗拉姆的公司认为这违反了保密协议，阻止了它在会议论文集上发表；证明被压了数年，直到 2004 年才登在《复杂系统》期刊上——那本期刊的创办者正是沃尔弗拉姆本人。
这段公案没有干净的一方：沃尔弗拉姆一方的说法是，证明规则 110 通用本就是库克受雇要做的工作。它值得写进来，是因为它提醒一件与元胞自动机无关的事——一个数学结果什么时候能被人读到，有时取决于合同而不是逻辑。