81. B5算法世界：简单规则产生复杂世界

Wolfram 对初等元胞自动机进行了穷尽式的研究，向人们展示了「简单规则产生复杂世界」这一事实。

【关键词】

元胞自动机，图灵完备，遗传算法

【正文】

你好，欢迎来到《KK 对话未来》！

这周我们的主题是算法世界。先敲下小黑板，不是要划重点，而是提醒你，今天的内容会有些硬。

说到算法，前不久有个小故事：我有个朋友写了篇文章，说不管是 AlphaGo 还是 AlphaGo Zero，都没什么可怕的，毕竟算法是人写的，如果用个公式来概括的话，就是「程序员 + AlphaGo > 人类棋手」。我就挑战了他一下，问他，如果「程序员 + AlphaGo > 程序员」会怎么样？他回答说，这个问题得好好想想。

其实，我是跟我朋友开了个玩笑，玩了一个小把戏。「写算法的人写出的算法是否能够超过写算法的人」，类似这样的判定性问题，现有的计算机是回答不了的。这个跟计算机的计算速度和内存都没有关系，而是由现有计算机的数学定义决定了的，是被计算机科学的奠基者之一图灵所证明了的。所以，我们目前的计算机技术从根本上来讲，就不是万能的；你也用不着担心，有一天计算机会统治世界。

但计算科学确实在帮助我们越来越深刻地认识这个世界，认识这个世界运转的一些基本规律。今天我们要讲的，就是「简单规则产生复杂世界」这样一条基本规律。

还是先从一个人说起，这个人叫斯蒂芬·沃尔夫勒姆（Stephen Wolfram）。说起这个人，那可是我的偶像。我在美国念书和在 Oracle 工作期间，凡是碰到任何不清楚的数学概念或数学问题时，都会去一个网站上找答案，几乎没有找不到的。这个网站就是 Wolfram 办的。后来又知道，有一套非常非常好用的数学工具软件，叫 Mathematica，也是 Wolfram 开发的。所以我对这个人是佩服得不行不行的。

Wolfram 是个天才。但他在上小学的时候，对算术这门课却非常吃力。到了12岁的时候，他自己编了一部关于物理学的词典；在13、4岁的时候，他写过三本关于粒子物理学的书，虽然都没有出版，但他的人生从此就开挂了。他在 21岁的时候成为了麦克阿瑟天才奖的首批获奖者之一，而且是那批获奖者里最年轻的一位。

他从上世纪八十年代起，对元胞自动机产生了很强烈的兴趣，后来用十年时间，写了一本关于初等元胞自动机的专著，书名叫做《A New Kind of Science》，翻译过来就是《一种新科学》。

那有必要讲一下初等元胞自动机是怎么回事：

你可以想象一条由很多小方格连接成的带子。每个小方格可以有黑白两种颜色，而且可以按照一定的规则随时间发生改变。什么样的规则呢？可以有很多不同的规则，但这些规则必须要符合一条规则，也就是规则的规则。这条规则的规则是这么说的：

任意一个方格，在下一时间点的颜色，是由这个方格和相邻两个方格在这一时间点的颜色所决定的。

有了这条规则的规则，那我们就可以穷举出初等元胞自动机的所有规则，一共有256种。Wolfram给这256种规则编了号，从0到255。然后他对每种规则下，带子上的方格颜色是如何演化的都做了研究，并且在《A New Kind of Science》这本书里一一列举了出来。

通过这种穷尽式的研究，他发现，绝大多数规则所产生的结果没什么有趣的：有的很快就进入了死亡状态，也就是不会再有任何变化；有的会形成一定的模式，所谓「模式」，不是不变化，而是在一些状态之间循环。但有两条规则产生了很有趣的结果：一条是30号规则，产生了完全无序、完全随机的演化过程，另一条是110号规则，演化过程是介于无序和有序之间，显得非常复杂。

后来 Wolfram 的一个助手，叫马修·库克（Matthew Cook），证明了110号规则是图灵完备的，意思就是说，这条规则下的元胞自动机可以模拟任何算法。

说到这儿，还有一段小插曲：Wolfram 早在1985年的时候，就提出一个猜想，认为110号规则是图灵完备的，但他自己一直未能给出严格的证明。马修·库克在2000年的时候证明了他的猜想，并且把证明过程发给了桑塔菲研究所（Santa Fe Institute）。如果你对复杂科学有所了解的话，应该知道桑塔菲研究所是复杂科学的圣地。马修·库克这么做，违反了他和 Wolfram 之间的约定。Wolfram 就通过法律手段，阻止了马修·库克公开发表他的证明。2002年 Wolfram 的《A New Kind of Science》出版时，书中有提及马修·库克的证明思路。到了2004年，Wolfram 终于允许马修·库克把他的证明发表在 Wolfram 主办的杂志《Complex System（复杂系统）》上。

110号规则是图灵完备这件事情，证明了「简单规则产生复杂世界」这一信念。其实，对任何从事复杂科学研究的人来说，这都是一条基本信念。Wolfram 的贡献就在于，他向人们展示了，这不仅仅只是信念，而且是事实。

其实我们从 Wolfram 身上也可以学到一些东西。如果你仔细琢磨他的人生故事，你会发现，他用了很多笨功夫：比如说，编一本物理学词典，建一个数学知识的大百科网站，也包括他对初等元胞自动机所做的穷尽式的研究。这些工作从某种意义上讲，都是体力活。但 Wolfram 正是通过这些笨功夫，实现了他的开挂人生。我们在后面的课中还会再提到他。

讲到这儿，你可能会有一个问题：在初等元胞自动机的256条规则中，只有一条能够产生出足够的复杂性。即使我们承认「简单规则产生复杂世界」，那这种概率是不是也太低了些？

其实并不低。别忘了，世界不是串行的，而是并行的。当很多规则都同时进行演化时，达尔文的自然选择理论仍然适用。也就是说，那些能产生足够复杂性的规则会存活下来，并主导世界的演化。

这也正是遗传算法的核心思想。遗传算法的发明者约翰·霍兰德正是从进化中得到了启发，设计出了遗传算法。他认为，人类的学习在本质上就是适应性的一个特例。关于这点，我们在之前《学习的本质是模仿和适应》那节课中已经讲过了。

好，这就是今天的全部内容。谢谢收听！