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

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

倍速播放下载收听

00:00
09:26

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条规则中,只有一条能够产生出足够的复杂性。即使我们承认「简单规则产生复杂世界」,那这种概率是不是也太低了些?


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


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


好,这就是今天的全部内容。谢谢收听!

评论

    还没有评论,快来发表第一个评论!

打开喜马拉雅,发表评论