每年，Wolfram Research公司都要舉辦一次暑期學(xué)校（Wolfram Summer School）[1]，交流在所謂「新科學(xué)」（New Kind of Science）領(lǐng)域的進(jìn)展與觀點(diǎn)。這個(gè)活動(dòng)至今已經(jīng)舉辦了13年，而每一年都會(huì)涉及的一個(gè)內(nèi)容，就是「復(fù)雜」本身——什么是復(fù)雜？復(fù)雜有有沒有極限？

為了回答這個(gè)問題，Wolfram在2002年專門出版了一本一千余頁的煌煌巨著來闡述他的研究——《A New Kind of Science》（中文：一種新科學(xué)）。而這本書的「高潮」之處，則在于最后一章的「計(jì)算等價(jià)性原理」（The Principle of Computational Equivalence）。

計(jì)算等價(jià)性原理（The Principle of Computational Equivalence）簡(jiǎn)單來說，就是認(rèn)為任何看起來比較復(fù)雜的系統(tǒng)（流體、社會(huì)系統(tǒng)、蟻群，等等），他們的復(fù)雜度都是相同的，而且都達(dá)到了復(fù)雜性的極限——它們的復(fù)雜度，與宇宙中其他極為復(fù)雜的系統(tǒng)，例如大腦，是相同的。而進(jìn)一步的，這個(gè)原理似乎從計(jì)算的視角，回答了「人能否理解宇宙」，這樣的「終極問題」。

而要理解這個(gè)宏大的原理、理解這個(gè)關(guān)于「復(fù)雜性」的原理，則需要從一個(gè)最簡(jiǎn)單的系統(tǒng)出發(fā)——元胞自動(dòng)機(jī)。

元胞自動(dòng)機(jī) Cellular Automata

二十世紀(jì)四十年代，馮·諾依曼在研究自復(fù)制機(jī)[2]的時(shí)候，提出了「元胞自動(dòng)機(jī)」的概念。元胞自動(dòng)機(jī)是一個(gè)根據(jù)特定規(guī)則演化的離散系統(tǒng)。Wolfram則考慮了一個(gè)最簡(jiǎn)單的元胞自動(dòng)機(jī)，如下圖所示，我們稱之為「基礎(chǔ)元胞自動(dòng)機(jī)」（Elementary Cellular Automata，ECA）。

基礎(chǔ)元胞自動(dòng)機(jī)，是一個(gè)在一維空間上，離散演化的系統(tǒng)，橫軸是空間，縱軸是時(shí)間。在給定一個(gè)初始狀態(tài)（第一行）之后，系統(tǒng)按照最下面的規(guī)則演化——按照規(guī)則的第六條：（黑色為1，白色為0），可以知道，第一行的黑色方塊，在下一步的演化之中，也是黑色。上圖完全由這八個(gè)簡(jiǎn)單的規(guī)則演化而來。這里所謂「30號(hào)」，也是從規(guī)則得到的，將八個(gè)規(guī)則按順序排列，得到01字串，將之視為一個(gè)二進(jìn)制數(shù)00011110，那么很容易算得，。0~255，每一個(gè)數(shù)字對(duì)應(yīng)一個(gè)規(guī)則，后面我們會(huì)一直使用這種表示方法。

如果我們延長(zhǎng)演化的步數(shù)，比如128步，可以發(fā)現(xiàn)，其行為變得極為復(fù)雜：

我們可以嘗試其他很多規(guī)則，會(huì)發(fā)現(xiàn)其行為非常豐富：

這里展現(xiàn)的系統(tǒng)，都基于極為簡(jiǎn)單規(guī)則，而卻能產(chǎn)生出非常豐富的行為。有的系統(tǒng)，甚至可以作為隨機(jī)數(shù)生成器來使用[3]。上面的這些事實(shí)，給我們的第一個(gè)啟發(fā)就是，「復(fù)雜」可以從極為簡(jiǎn)單的規(guī)則中涌現(xiàn)出來。那么，就可以定性解釋「為何自然界中，復(fù)雜行為如此常見」——只要任何規(guī)則、動(dòng)力學(xué)機(jī)制，都包含了這些簡(jiǎn)單規(guī)則，那么它就有潛力產(chǎn)生復(fù)雜的行為。而由于上面規(guī)則之簡(jiǎn)單，使得很多規(guī)則更復(fù)雜的系統(tǒng)，都很容易將之包含進(jìn)去。

然而，這樣給人們帶來了一個(gè)問題：如何度量復(fù)雜性？復(fù)雜性的極限在哪里？

要回答這個(gè)問題，一個(gè)最自然的出發(fā)點(diǎn)，就是去尋找復(fù)雜性相同的系統(tǒng)。所謂「A與B復(fù)雜性相同」，從計(jì)算的角度看，就是認(rèn)為「A可以模擬B」，而「B也可以模擬A」。我們從這個(gè)問題內(nèi)的一部分開始：A系統(tǒng)模擬B系統(tǒng)。

無處不在的等價(jià)

在Wolfram的書中，他列舉了大量這樣的關(guān)系：元胞自動(dòng)機(jī)可以等價(jià)于各種其他系統(tǒng)的行為。從數(shù)字電路，到數(shù)論，再到邏輯代數(shù)，而后一路推進(jìn)，到通用圖靈機(jī)——可以模擬一切可計(jì)算系統(tǒng)的系統(tǒng)。

一個(gè)最簡(jiǎn)單的例子，就是規(guī)則132：

這個(gè)系統(tǒng)完成了如下的計(jì)算：

其中n就是第一行黑色方塊的數(shù)量。經(jīng)過至多次演化之后，得到f(n)。

對(duì)于代數(shù)運(yùn)算，元胞自動(dòng)機(jī)顯然可以做的更多。

它可以計(jì)算n的平方：

下面的元胞自動(dòng)機(jī)規(guī)則比上面要稍微復(fù)雜一些。

同樣，給定初始第一行黑色方塊的數(shù)量n，系統(tǒng)演化到穩(wěn)定之后，其黑色方塊的數(shù)量就是. 也就是說，它等價(jià)于：

元胞自動(dòng)機(jī)甚至可以用來尋找素?cái)?shù)：

其中左邊的每一條白線，都對(duì)應(yīng)著一個(gè)素?cái)?shù)。也就是說，這個(gè)元胞自動(dòng)機(jī)，等價(jià)于運(yùn)算：

既然我們要討論「無處不在的等價(jià)」，那么僅僅代數(shù)、數(shù)論運(yùn)算，是遠(yuǎn)遠(yuǎn)不夠的。

基本的邏輯運(yùn)算：

使用簡(jiǎn)單規(guī)則的元胞自動(dòng)機(jī)，可以支持與、或，以及由其構(gòu)造出的各種運(yùn)算：

可以看到，下面的規(guī)則列表比之前長(zhǎng)了很多。同時(shí)，基礎(chǔ)元胞自動(dòng)機(jī)中的146，190號(hào)規(guī)則，可以進(jìn)行邏輯運(yùn)算：

上面的這些元胞自動(dòng)機(jī)，是溝通簡(jiǎn)單與復(fù)雜的橋梁之一——通過代數(shù)、數(shù)論，以及邏輯運(yùn)算，可以構(gòu)造出復(fù)雜度遠(yuǎn)遠(yuǎn)超過規(guī)則的行為。

從等價(jià)到普適

從上面的例子，人們很自然的會(huì)想到，是否存在一個(gè)系統(tǒng)，規(guī)則極為簡(jiǎn)單，而卻能模擬其它任何系統(tǒng)[4]呢？

一個(gè)最初的想法，就是用更復(fù)雜的元胞自動(dòng)機(jī)，去模擬所有基礎(chǔ)元胞自動(dòng)機(jī)。事實(shí)表明，這是可以的，但其規(guī)則極為復(fù)雜，這里不詳述其規(guī)則，只大致介紹一下：

通過設(shè)定初值，即第一行元胞顏色的順序，它可以模擬所有基礎(chǔ)元胞自動(dòng)機(jī)，如上圖，分別是254號(hào)、90號(hào)和30號(hào)。

然而，這樣「工匠」一般的搜尋，對(duì)于理論來說，并沒有太多的助益——無非是找到了很多等價(jià)的系統(tǒng)而已。然而，后來的一個(gè)突破性進(jìn)展，直接導(dǎo)致了「計(jì)算等價(jià)性原理」的誕生。

在2000年，Wolfram的一個(gè)助手，Matthew Cook，證明了基礎(chǔ)元胞自動(dòng)機(jī)中的規(guī)則110是圖靈完備的[5]。

就是上圖的這種元胞自動(dòng)機(jī)。同樣的，使用八個(gè)參數(shù)確定出的簡(jiǎn)單規(guī)則。

為了說明這個(gè)研究的意義，需要先簡(jiǎn)單說一下「通用圖靈機(jī)」（UTM）是什么，「圖靈完備」是什么。一個(gè)直觀的想象就是，通用圖靈機(jī)（UTM）是一個(gè)抽象的電腦。是只用來描述電腦計(jì)算能力的一個(gè)抽象模型。從另一個(gè)角度來說，電腦上能進(jìn)行的計(jì)算，圖靈機(jī)都能進(jìn)行。圖靈機(jī)是目前可實(shí)現(xiàn)的計(jì)算系統(tǒng)中，計(jì)算能力最強(qiáng)的系統(tǒng)（包括量子計(jì)算機(jī)，也是圖靈機(jī)）。而所謂「圖靈完備」，簡(jiǎn)單的說，就是一個(gè)系統(tǒng)，等價(jià)于通用圖靈機(jī)。

那么，既然110號(hào)規(guī)則已經(jīng)是圖靈完備的了，它便可以運(yùn)行任何程序——從最簡(jiǎn)單的，到最復(fù)雜的。而既然它可以運(yùn)行最為復(fù)雜的程序，那么這個(gè)系統(tǒng)本身，是不是可以認(rèn)為，已經(jīng)達(dá)到了復(fù)雜性的極限了呢？Wolfram 給出的回答是：「是的，UTM就是復(fù)雜性的極限，而且很容易達(dá)到」。

另一個(gè)需要注意的，就是110號(hào)規(guī)則本身非常簡(jiǎn)單——這意味著，其他規(guī)則稍稍復(fù)雜一些的系統(tǒng)，其規(guī)則本身，很有可能已經(jīng)包含了110號(hào)元胞自動(dòng)機(jī)。這暗示著，有大量的系統(tǒng)是通用圖靈機(jī)，他們的復(fù)雜度相同，都是計(jì)算復(fù)雜性的極限。

那么問題就來了，一個(gè)系統(tǒng)很容易包含其他系統(tǒng)的行為嗎？最近的一個(gè)研究[6]發(fā)現(xiàn)，當(dāng)我們逐漸增大觀察系統(tǒng)的標(biāo)尺時(shí)（實(shí)空間重整化），會(huì)有越來越多的系統(tǒng)能夠互相模擬，或者單向的模擬。

普通的元胞自動(dòng)機(jī)，以單個(gè)元胞為單元，即0或1. 但如果我們引入重整化的思想，將兩個(gè)，或者三個(gè)元胞作為一個(gè)單元，比如我們定義：

這時(shí)，初值只有{1,1}和{0,0}的排列，而不會(huì)出現(xiàn){...,0,1,0,...}這樣的情況。我們稱這個(gè)過程為「編譯」，而這個(gè)變換的規(guī)則就是「編譯器」（compiler）。這時(shí)我們發(fā)現(xiàn)，94號(hào)元胞自動(dòng)機(jī)，可以展現(xiàn)出90號(hào)元胞自動(dòng)機(jī)的行為：

這意味著，94號(hào)規(guī)則，包含了90號(hào)規(guī)則的行為。這里我們是將兩個(gè)元胞合成一個(gè)單元，如果是「三變一」、「四變一」呢？研究發(fā)現(xiàn)，當(dāng)這個(gè)數(shù)字增長(zhǎng)的時(shí)候，能夠互相模擬的系統(tǒng)越來越多：

上圖中，橫軸是編譯器的尺寸，而縱軸則是能夠互相模擬的系統(tǒng)的數(shù)量——即出現(xiàn)的頻率。不同顏色線，代表了不同的元胞自動(dòng)機(jī)族。這張圖表明，隨著編譯器尺寸的增加，系統(tǒng)之間，一方能模擬另一方的概率趨近于1，或者一個(gè)很接近1的值。

這個(gè)結(jié)果非常重要！這暗示了，在自然界之中，系統(tǒng)間的模擬，也是非常常見的。

這樣再回到前面的一段話：

另一個(gè)需要注意的，就是110號(hào)規(guī)則本身非常簡(jiǎn)單——這意味著，其他規(guī)則稍稍復(fù)雜一些的系統(tǒng)，其規(guī)則本身，很有可能已經(jīng)包含了110號(hào)元胞自動(dòng)機(jī)。這暗示著，有大量的系統(tǒng)是通用圖靈機(jī)，他們的復(fù)雜度相同，都是計(jì)算復(fù)雜性的極限。

現(xiàn)在只要再有一個(gè)假設(shè)，就可以得到計(jì)算等價(jià)性原理了：

「宇宙就是一個(gè)計(jì)算機(jī)」

很多人可能覺得這一句話很多余，因?yàn)樗坪踔皇且粋€(gè)看世界的不同視角罷了。但是需要注意的是，這個(gè)假設(shè)，暗含了一個(gè)很強(qiáng)的要求：宇宙中所有的行為、現(xiàn)象、數(shù)值，都是可計(jì)算的，是可以在圖靈機(jī)上，通過運(yùn)行程序而得到的。

舉個(gè)例子說明這個(gè)假設(shè)的必要性：

2015年，一項(xiàng)研究表明，二維無限大晶格材料的能隙是不可計(jì)算的[7]。

然而，在我們目前的認(rèn)知之中，宇宙間不存在無限大的物體，而那項(xiàng)研究也證明了，任何有限大的二維晶格，其能隙都是可計(jì)算的——目前為止，還沒有真實(shí)的物理體系被證明是不可計(jì)算的。

有了「宇宙就是一個(gè)計(jì)算機(jī)」這個(gè)假設(shè)之后，我們便可以提出「計(jì)算等價(jià)性原理」了。Wolfram的表述是：

幾乎所有看起來不那么簡(jiǎn)單過程，他們的復(fù)雜度都是相同的。（Almost all processes that are not obviously simple can be viewed as computations of equivalent sophistication.）

而且，「復(fù)雜度的極限是很容易達(dá)到的」，只要規(guī)則稍稍豐富一點(diǎn)點(diǎn)，系統(tǒng)就會(huì)展現(xiàn)出宇宙間最復(fù)雜的行為——通用圖靈機(jī)的各種行為。這意味著，之所以我們能夠在宇宙中看到如此多、如此豐富的復(fù)雜行為，其根本原因是，他們的動(dòng)力學(xué)機(jī)制，支持圖靈完備的運(yùn)算——從而包含了從最簡(jiǎn)單，到最復(fù)雜的所有行為。

基于計(jì)算等價(jià)性原理的另一個(gè)推論就是「人可以理解宇宙」，或者是，漸進(jìn)地理解宇宙。如果我們從計(jì)算的視角來定義「理解」，我們就能得到這個(gè)推論：我們定義A「理解」B，是A能夠在大腦，或者自身的某個(gè)系統(tǒng)之中，具象，或者抽象的重現(xiàn)出B。即A能模擬B、A能運(yùn)行B。

我們說「我理解一個(gè)物理定律」，最基本的，就是能夠在大腦中通過物理圖像、公式，來描述某個(gè)規(guī)則。

如果計(jì)算等價(jià)性原理是錯(cuò)的，那么相對(duì)簡(jiǎn)單的大腦如何理解相對(duì)復(fù)雜的宇宙呢？而如果承認(rèn)計(jì)算等價(jià)性原理，我們就可以說，大腦的復(fù)雜性是與宇宙相同的，唯一的限制是容量，但我們依舊可以用計(jì)算機(jī)來拓展它的理解力。

Wolfram曾在果殼的專訪[8]中說：「宇宙的本質(zhì)是計(jì)算」?？峙缕渖钜庖苍谟诖恕?/p>

參考文獻(xiàn)

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 : 指可計(jì)算的系統(tǒng)；

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)，科普版見：不可解的物理學(xué)難題，源于數(shù)學(xué)核心的悖論

8 : 斯蒂芬·沃爾夫勒姆：宇宙的本質(zhì)是計(jì)算