首发于鼁鸣堂
「复杂」的极限在哪里:Wolfram与他的「计算等价性原理」

「复杂」的极限在哪里:Wolfram与他的「计算等价性原理」

每年,Wolfram Research公司都要举办一次暑期学校(Wolfram Summer School)[1],交流在所谓「新科学」(New Kind of Science)领域的进展与观点。这个活动至今已经举办了13年,而每一年都会涉及的一个内容,就是「复杂」本身——什么是复杂?复杂有有没有极限?


> Stephen Wolfram 照片

为了回答这个问题,Wolfram在2002年专门出版了一本一千余页的煌煌巨著来阐述他的研究——《A New Kind of Science》(中文:一种新科学)。而这本书的「高潮」之处,则在于最后一章的「计算等价性原理」(The Principle of Computational Equivalence)。

> 图1:扎克伯格桌上的《A New Kind of Science》,参见知乎问题:通过这张照片能看出 Mark Zuckerberg 最近在读哪些书?

计算等价性原理(The Principle of Computational Equivalence)简单来说,就是认为任何看起来比较复杂的系统(流体、社会系统、蚁群,等等),他们的复杂度都是相同的,而且都达到了复杂性的极限——它们的复杂度,与宇宙中其他极为复杂的系统,例如大脑,是相同的。而进一步的,这个原理似乎从计算的视角,回答了「人能否理解宇宙」,这样的「终极问题」。

而要理解这个宏大的原理、理解这个关于「复杂性」的原理,则需要从一个最简单的系统出发——元胞自动机。

元胞自动机 Cellular Automata

二十世纪四十年代,冯·诺依曼在研究自复制机[2]的时候,提出了「元胞自动机」的概念。元胞自动机是一个根据特定规则演化的离散系统。Wolfram则考虑了一个最简单的元胞自动机,如下图所示,我们称之为「基础元胞自动机」(Elementary Cellular Automata,ECA)。


> 图2:30号基础元胞自动机。

基础元胞自动机,是一个在一维空间上,离散演化的系统,横轴是空间,纵轴是时间。在给定一个初始状态(第一行)之后,系统按照最下面的规则演化——按照规则的第六条:(0,1,0)\to 1(黑色为1,白色为0),可以知道,第一行的黑色方块,在下一步的演化之中,也是黑色。上图完全由这八个简单的规则演化而来。这里所谓「30号」,也是从规则得到的,将八个规则按顺序排列,得到01字串,将之视为一个二进制数00011110,那么很容易算得,2^4 + 2^3 + 2^2 + 2^1 = 30。0~255,每一个数字对应一个规则,后面我们会一直使用这种表示方法。

如果我们延长演化的步数,比如128步,可以发现,其行为变得极为复杂:

> 图3:演化128步后的时空图。

我们可以尝试其他很多规则,会发现其行为非常丰富:


> 图4:六种不同的基础元胞自动机,他们行为迥异,混乱、秩序,分形,展现出了非常丰富的行为。

这里展现的系统,都基于极为简单规则,而却能产生出非常丰富的行为。有的系统,甚至可以作为随机数生成器来使用[3]。上面的这些事实,给我们的第一个启发就是,「复杂」可以从极为简单的规则中涌现出来。那么,就可以定性解释「为何自然界中,复杂行为如此常见」——只要任何规则、动力学机制,都包含了这些简单规则,那么它就有潜力产生复杂的行为。而由于上面规则之简单,使得很多规则更复杂的系统,都很容易将之包含进去。

然而,这样给人们带来了一个问题:如何度量复杂性?复杂性的极限在哪里?

要回答这个问题,一个最自然的出发点,就是去寻找复杂性相同的系统。所谓「A与B复杂性相同」,从计算的角度看,就是认为「A可以模拟B」,而「B也可以模拟A」。我们从这个问题内的一部分开始:A系统模拟B系统。

无处不在的等价

在Wolfram的书中,他列举了大量这样的关系:元胞自动机可以等价于各种其他系统的行为。从数字电路,到数论,再到逻辑代数,而后一路推进,到通用图灵机——可以模拟一切可计算系统的系统。

一个最简单的例子,就是规则132


这个系统完成了如下的计算:

f(n) = \begin{cases}<br>0 & , n\text{ is even}\\<br>1 & , n\text{ is odd}<br>\end{cases}

其中n就是第一行黑色方块的数量。经过至多n/2+1次演化之后,得到f(n)。

对于代数运算,元胞自动机显然可以做的更多。

它可以计算n的平方:

下面的元胞自动机规则比上面要稍微复杂一些。


同样,给定初始第一行黑色方块的数量n,系统演化到稳定之后,其黑色方块的数量就是n^2. 也就是说,它等价于:

f(n) = n^2

元胞自动机甚至可以用来寻找素数:


其中左边的每一条白线,都对应着一个素数。也就是说,这个元胞自动机,等价于运算:

f(n) = p(n)

既然我们要讨论「无处不在的等价」,那么仅仅代数、数论运算,是远远不够的。

基本的逻辑运算:

使用简单规则的元胞自动机,可以支持与、或,以及由其构造出的各种运算:


可以看到,下面的规则列表比之前长了很多。同时,基础元胞自动机中的146,190号规则,可以进行逻辑运算:

上面的这些元胞自动机,是沟通简单与复杂的桥梁之一——通过代数、数论,以及逻辑运算,可以构造出复杂度远远超过规则的行为。

从等价到普适

从上面的例子,人们很自然的会想到,是否存在一个系统,规则极为简单,而却能模拟其它任何系统[4]呢?

一个最初的想法,就是用更复杂的元胞自动机,去模拟所有基础元胞自动机。事实表明,这是可以的,但其规则极为复杂,这里不详述其规则,只大致介绍一下:


通过设定初值,即第一行元胞颜色的顺序,它可以模拟所有基础元胞自动机,如上图,分别是254号、90号和30号。

然而,这样「工匠」一般的搜寻,对于理论来说,并没有太多的助益——无非是找到了很多等价的系统而已。然而,后来的一个突破性进展,直接导致了「计算等价性原理」的诞生。

在2000年,Wolfram的一个助手,Matthew Cook,证明了基础元胞自动机中的规则110是图灵完备的[5]


就是上图的这种元胞自动机。同样的,使用八个参数确定出的简单规则。

为了说明这个研究的意义,需要先简单说一下「通用图灵机」(UTM)是什么,「图灵完备」是什么。一个直观的想象就是,通用图灵机(UTM)是一个抽象的电脑。是只用来描述电脑计算能力的一个抽象模型。从另一个角度来说,电脑上能进行的计算,图灵机都能进行。图灵机是目前可实现的计算系统中,计算能力最强的系统(包括量子计算机,也是图灵机)。而所谓「图灵完备」,简单的说,就是一个系统,等价于通用图灵机。

那么,既然110号规则已经是图灵完备的了,它便可以运行任何程序——从最简单的,到最复杂的。而既然它可以运行最为复杂的程序,那么这个系统本身,是不是可以认为,已经达到了复杂性的极限了呢?Wolfram 给出的回答是:「是的,UTM就是复杂性的极限,而且很容易达到」。

另一个需要注意的,就是110号规则本身非常简单——这意味着,其他规则稍稍复杂一些的系统,其规则本身,很有可能已经包含了110号元胞自动机。这暗示着,有大量的系统是通用图灵机,他们的复杂度相同,都是计算复杂性的极限。

那么问题就来了,一个系统很容易包含其他系统的行为吗?最近的一个研究[6]发现,当我们逐渐增大观察系统的标尺时(实空间重整化),会有越来越多的系统能够互相模拟,或者单向的模拟。

普通的元胞自动机,以单个元胞为单元,即0或1. 但如果我们引入重整化的思想,将两个,或者三个元胞作为一个单元,比如我们定义:

1\leftrightarrow \{1,1\}\\<br>0\leftrightarrow \{0,0\}

这时,初值只有{1,1}和{0,0}的排列,而不会出现{...,0,1,0,...}这样的情况。我们称这个过程为「编译」,而这个变换的规则就是「编译器」(compiler)。这时我们发现,94号元胞自动机,可以展现出90号元胞自动机的行为:


这意味着,94号规则,包含了90号规则的行为。这里我们是将两个元胞合成一个单元,如果是「三变一」、「四变一」呢?研究发现,当这个数字增长的时候,能够互相模拟的系统越来越多:


上图中,横轴是编译器的尺寸,而纵轴则是能够互相模拟的系统的数量——即出现的频率。不同颜色线,代表了不同的元胞自动机族。这张图表明,随着编译器尺寸的增加,系统之间,一方能模拟另一方的概率趋近于1,或者一个很接近1的值。

这个结果非常重要!这暗示了,在自然界之中,系统间的模拟,也是非常常见的。

这样再回到前面的一段话:

另一个需要注意的,就是110号规则本身非常简单——这意味着,其他规则稍稍复杂一些的系统,其规则本身,很有可能已经包含了110号元胞自动机。这暗示着,有大量的系统是通用图灵机,他们的复杂度相同,都是计算复杂性的极限。

现在只要再有一个假设,就可以得到计算等价性原理了:

「宇宙就是一个计算机」

很多人可能觉得这一句话很多余,因为似乎只是一个看世界的不同视角罢了。但是需要注意的是,这个假设,暗含了一个很强的要求:宇宙中所有的行为、现象、数值,都是可计算的,是可以在图灵机上,通过运行程序而得到的。

举个例子说明这个假设的必要性:

2015年,一项研究表明,二维无限大晶格材料的能隙是不可计算的[7]。

然而,在我们目前的认知之中,宇宙间不存在无限大的物体,而那项研究也证明了,任何有限大的二维晶格,其能隙都是可计算的——目前为止,还没有真实的物理体系被证明是不可计算的。

有了「宇宙就是一个计算机」这个假设之后,我们便可以提出「计算等价性原理」了。Wolfram的表述是:

几乎所有看起来不那么简单过程,他们的复杂度都是相同的。(Almost all processes that are not obviously simple can be viewed as computations of equivalent sophistication.)

而且,「复杂度的极限是很容易达到的」,只要规则稍稍丰富一点点,系统就会展现出宇宙间最复杂的行为——通用图灵机的各种行为。这意味着,之所以我们能够在宇宙中看到如此多、如此丰富的复杂行为,其根本原因是,他们的动力学机制,支持图灵完备的运算——从而包含了从最简单,到最复杂的所有行为。

基于计算等价性原理的另一个推论就是「人可以理解宇宙」,或者是,渐进地理解宇宙。如果我们从计算的视角来定义「理解」,我们就能得到这个推论:我们定义A「理解」B,是A能够在大脑,或者自身的某个系统之中,具象,或者抽象的重现出B。即A能模拟B、A能运行B。

我们说「我理解一个物理定律」,最基本的,就是能够在大脑中通过物理图像、公式,来描述某个规则。

如果计算等价性原理是错的,那么相对简单的大脑如何理解相对复杂的宇宙呢?而如果承认计算等价性原理,我们就可以说,大脑的复杂性是与宇宙相同的,唯一的限制是容量,但我们依旧可以用计算机来拓展它的理解力。

Wolfram曾在果壳的专访[8]中说:「宇宙的本质是计算」。恐怕其深意也在于此。


文章/回答精选集:

复杂性科学 - 生活×物理 - 艺术×数理 - 科研评论

公众号/微博:「复杂鱼塘」,complex-zyb

Bilibili:复杂鱼塘


0 题图:来自commons.wikimedia.org/w,公共版权;

1 : Wolfram Summer School


2 : Neumann, J. V. (1966). Theory of Self-Reproducing
Automata. (A. W. Burks, Ed.). Champaign, IL, USA: University of Illinois
Press.

3 : Tomassini, M., Sipper, M., & Perrenoud, M. (2000).
On the generation of high-quality random numbers by two-dimensional cellular
automata. IEEE Transactions on Computers, 49(10), 1146–1151.

4 : 指可计算的系统;

5 : Cook, M. (2004). Universality in elementary cellular
automata. Complex Systems, 15(1), 1–40.

6 : Jürgen Riedel, & Hector Zenil. (n.d.).
Cross-boundary Behavioural Reprogrammability of Cellular Automata from
Emulation Networks.

7 : [1502.04573] Undecidability of the Spectral Gap (full version),科普版见:不可解的物理学难题,源于数学核心的悖论

8 : 【果壳网专访】斯蒂芬·沃尔夫勒姆:宇宙的本质是计算 | 科学人 | 果壳网 科技有意思

编辑于 2019-04-26 09:48