每年，Wolfram Research公司都要舉辦一次暑期學校（Wolfram Summer School）[1]，交流在所謂「新科學」（New Kind of Science）領(lǐng)域的進展與觀點。這個活動至今已經(jīng)舉辦了13年，而每一年都會涉及的一個內(nèi)容，就是「復(fù)雜」本身——什么是復(fù)雜？復(fù)雜有有沒有極限？
Stephen Wolfram照片
為了回答這個問題，Wolfram在2002年專門出版了一本一千余頁的煌煌巨著來闡述他的研究——《A New Kind of Science》（中文：一種新科學）。而這本書的「高潮」之處，則在于最后一章的「計算等價性原理」（The Principle of Computational Equivalence）。
扎克伯格桌上的《A New Kind of Science》
計算等價性原理（The Principle of Computational Equivalence）簡單來說，就是認為任何看起來比較復(fù)雜的系統(tǒng)（流體、社會系統(tǒng)、蟻群，等等），他們的復(fù)雜度都是相同的，而且都達到了復(fù)雜性的極限——它們的復(fù)雜度，與宇宙中其他極為復(fù)雜的系統(tǒng)，例如大腦，是相同的。而進一步的，這個原理似乎從計算的視角，回答了「人能否理解宇宙」，這樣的「終極問題」。
而要理解這個宏大的原理、理解這個關(guān)于「復(fù)雜性」的原理，則需要從一個最簡單的系統(tǒng)出發(fā)——元胞自動機。
二十世紀四十年代，馮·諾依曼在研究自復(fù)制機[2]的時候，提出了「元胞自動機」的概念。元胞自動機是一個根據(jù)特定規(guī)則演化的離散系統(tǒng)。Wolfram則考慮了一個最簡單的元胞自動機，如下圖所示，我們稱之為「基礎(chǔ)元胞自動機」（Elementary Cellular Automata，ECA）。
圖2：30號基礎(chǔ)元胞自動機。
基礎(chǔ)元胞自動機，是一個在一維空間上，離散演化的系統(tǒng)，橫軸是空間，縱軸是時間。在給定一個初始狀態(tài)（第一行）之后，系統(tǒng)按照最下面的規(guī)則演化——按照規(guī)則的第六條：（黑色為1，白色為0），可以知道，第一行的黑色方塊，在下一步的演化之中，也是黑色。上圖完全由這八個簡單的規(guī)則演化而來。這里所謂「30號」，也是從規(guī)則得到的，將八個規(guī)則按順序排列，得到01字串，將之視為一個二進制數(shù)00011110，那么很容易算得，。0~255，每一個數(shù)字對應(yīng)一個規(guī)則，后面我們會一直使用這種表示方法。
如果我們延長演化的步數(shù)，比如128步，可以發(fā)現(xiàn)，其行為變得極為復(fù)雜：
圖3：演化128步后的時空圖
我們可以嘗試其他很多規(guī)則，會發(fā)現(xiàn)其行為非常豐富：
圖4：六種不同的基礎(chǔ)元胞自動機，他們行為迥異，混亂、秩序，分形，展現(xiàn)出了非常豐富的行為。
這里展現(xiàn)的系統(tǒng)，都基于極為簡單規(guī)則，而卻能產(chǎn)生出非常豐富的行為。有的系統(tǒng)，甚至可以作為隨機數(shù)生成器來使用[3]。上面的這些事實，給我們的第一個啟發(fā)就是，「復(fù)雜」可以從極為簡單的規(guī)則中涌現(xiàn)出來。那么，就可以定性解釋「為何自然界中，復(fù)雜行為如此常見」——只要任何規(guī)則、動力學機制，都包含了這些簡單規(guī)則，那么它就有潛力產(chǎn)生復(fù)雜的行為。而由于上面規(guī)則之簡單，使得很多規(guī)則更復(fù)雜的系統(tǒng)，都很容易將之包含進去。
然而，這樣給人們帶來了一個問題：如何度量復(fù)雜性？復(fù)雜性的極限在哪里？
要回答這個問題，一個最自然的出發(fā)點，就是去尋找復(fù)雜性相同的系統(tǒng)。所謂「A與B復(fù)雜性相同」，從計算的角度看，就是認為「A可以模擬B」，而「B也可以模擬A」。我們從這個問題內(nèi)的一部分開始：A系統(tǒng)模擬B系統(tǒng)。
在Wolfram的書中，他列舉了大量這樣的關(guān)系：元胞自動機可以等價于各種其他系統(tǒng)的行為。從數(shù)字電路，到數(shù)論，再到邏輯代數(shù)，而后一路推進，到通用圖靈機——可以模擬一切可計算系統(tǒng)的系統(tǒng)。
一個最簡單的例子，就是規(guī)則132：
規(guī)則132的演化圖
規(guī)則132的規(guī)則圖
這個系統(tǒng)完成了如下的計算：
如果n是偶數(shù)，則返回0；如果n是奇數(shù)，則返回1
其中n就是第一行黑色方塊的數(shù)量。經(jīng)過至多次演化之后，得到f(n)。
對于代數(shù)運算，元胞自動機顯然可以做的更多。
它可以計算n的平方：
下面的元胞自動機規(guī)則比上面要稍微復(fù)雜一些。
這個元胞自動機可以計算n的平方
同樣，給定初始第一行黑色方塊的數(shù)量n，系統(tǒng)演化到穩(wěn)定之后，其黑色方塊的數(shù)量就是. 也就是說，它等價于：
元胞自動機甚至可以用來尋找素數(shù)：
每一條白線就對應(yīng)一個素數(shù)
其中左邊的每一條白線，都對應(yīng)著一個素數(shù)。也就是說，這個元胞自動機，等價于運算：
既然我們要討論「無處不在的等價」，那么僅僅代數(shù)、數(shù)論運算，是遠遠不夠的。
基本的邏輯運算：
使用簡單規(guī)則的元胞自動機，可以支持與、或，以及由其構(gòu)造出的各種運算：
基本的邏輯運算
可以看到，下面的規(guī)則列表比之前長了很多。同時，基礎(chǔ)元胞自動機中的146，190號規(guī)則，可以進行邏輯運算：
上面的這些元胞自動機，是溝通簡單與復(fù)雜的橋梁之一——通過代數(shù)、數(shù)論，以及邏輯運算，可以構(gòu)造出復(fù)雜度遠遠超過規(guī)則的行為。
從上面的例子，人們很自然的會想到，是否存在一個系統(tǒng)，規(guī)則極為簡單，而卻能模擬其它任何系統(tǒng)[4]呢？
一個最初的想法，就是用更復(fù)雜的元胞自動機，去模擬所有基礎(chǔ)元胞自動機。事實表明，這是可以的，但其規(guī)則極為復(fù)雜，這里不詳述其規(guī)則，只大致介紹一下：
通過設(shè)定初值，即第一行元胞顏色的順序，它可以模擬所有基礎(chǔ)元胞自動機，如上圖，分別是254號、90號和30號。
然而，這樣「工匠」一般的搜尋，對于理論來說，并沒有太多的助益——無非是找到了很多等價的系統(tǒng)而已。然而，后來的一個突破性進展，直接導(dǎo)致了「計算等價性原理」的誕生。
在2000年，Wolfram的一個助手，Matthew Cook，證明了基礎(chǔ)元胞自動機中的規(guī)則110是圖靈完備的[5]。
110號元胞自動機的演化圖，它等價于通用計算機
110號元胞自動機的規(guī)則圖
就是上圖的這種元胞自動機。同樣的，使用八個參數(shù)確定出的簡單規(guī)則。
為了說明這個研究的意義，需要先簡單說一下「通用圖靈機」（UTM）是什么，「圖靈完備」是什么。一個直觀的想象就是，通用圖靈機（UTM）是一個抽象的電腦。是只用來描述電腦計算能力的一個抽象模型。從另一個角度來說，電腦上能進行的計算，圖靈機都能進行。圖靈機是目前可實現(xiàn)的計算系統(tǒng)中，計算能力最強的系統(tǒng)（包括量子計算機，也是圖靈機）。而所謂「圖靈完備」，簡單的說，就是一個系統(tǒng)，等價于通用圖靈機。
那么，既然110號規(guī)則已經(jīng)是圖靈完備的了，它便可以運行任何程序——從最簡單的，到最復(fù)雜的。而既然它可以運行最為復(fù)雜的程序，那么這個系統(tǒng)本身，是不是可以認為，已經(jīng)達到了復(fù)雜性的極限了呢？Wolfram 給出的回答是：「是的，UTM就是復(fù)雜性的極限，而且很容易達到」。
另一個需要注意的，就是110號規(guī)則本身非常簡單——這意味著，其他規(guī)則稍稍復(fù)雜一些的系統(tǒng)，其規(guī)則本身，很有可能已經(jīng)包含了110號元胞自動機。這暗示著，有大量的系統(tǒng)是通用圖靈機，他們的復(fù)雜度相同，都是計算復(fù)雜性的極限。
那么問題就來了，一個系統(tǒng)很容易包含其他系統(tǒng)的行為嗎？最近的一個研究[6]發(fā)現(xiàn)，當我們逐漸增大觀察系統(tǒng)的標尺時（實空間重整化），會有越來越多的系統(tǒng)能夠互相模擬，或者單向的模擬。
普通的元胞自動機，以單個元胞為單元，即0或1. 但如果我們引入重整化的思想，將兩個，或者三個元胞作為一個單元，比如我們定義：
這時，初值只有{1,1}和{0,0}的排列，而不會出現(xiàn){...,0,1,0,...}這樣的情況。我們稱這個過程為「編譯」，而這個變換的規(guī)則就是「編譯器」（compiler）。這時我們發(fā)現(xiàn)，94號元胞自動機，可以展現(xiàn)出90號元胞自動機的行為：
這意味著，94號規(guī)則，包含了90號規(guī)則的行為。這里我們是將兩個元胞合成一個單元，如果是「三變一」、「四變一」呢？研究發(fā)現(xiàn)，當這個數(shù)字增長的時候，能夠互相模擬的系統(tǒng)越來越多：
上圖中，橫軸是編譯器的尺寸，而縱軸則是能夠互相模擬的系統(tǒng)的數(shù)量——即出現(xiàn)的頻率。不同顏色線，代表了不同的元胞自動機族。這張圖表明，隨著編譯器尺寸的增加，系統(tǒng)之間，一方能模擬另一方的概率趨近于1，或者一個很接近1的值。
這個結(jié)果非常重要！這暗示了，在自然界之中，系統(tǒng)間的模擬，也是非常常見的。
這樣再回到前面的一段話：
另一個需要注意的，就是110號規(guī)則本身非常簡單——這意味著，其他規(guī)則稍稍復(fù)雜一些的系統(tǒng)，其規(guī)則本身，很有可能已經(jīng)包含了110號元胞自動機。這暗示著，有大量的系統(tǒng)是通用圖靈機，他們的復(fù)雜度相同，都是計算復(fù)雜性的極限。
現(xiàn)在只要再有一個假設(shè)，就可以得到計算等價性原理了：
很多人可能覺得這一句話很多余，因為似乎只是一個看世界的不同視角罷了。但是需要注意的是，這個假設(shè)，暗含了一個很強的要求：宇宙中所有的行為、現(xiàn)象、數(shù)值，都是可計算的，是可以在圖靈機上，通過運行程序而得到的。
舉個例子說明這個假設(shè)的必要性：
2015年，一項研究表明，二維無限大晶格材料的能隙是不可計算的[7]。
然而，在我們目前的認知之中，宇宙間不存在無限大的物體，而那項研究也證明了，任何有限大的二維晶格，其能隙都是可計算的——目前為止，還沒有真實的物理體系被證明是不可計算的。
有了「宇宙就是一個計算機」這個假設(shè)之后，我們便可以提出「計算等價性原理」了。Wolfram的表述是：
幾乎所有看起來不那么簡單過程，他們的復(fù)雜度都是相同的。（Almost all processes that are not obviously simple can be viewed as computations of equivalent sophistication.）
而且，「復(fù)雜度的極限是很容易達到的」，只要規(guī)則稍稍豐富一點點，系統(tǒng)就會展現(xiàn)出宇宙間最復(fù)雜的行為——通用圖靈機的各種行為。這意味著，之所以我們能夠在宇宙中看到如此多、如此豐富的復(fù)雜行為，其根本原因是，他們的動力學機制，支持圖靈完備的運算——從而包含了從最簡單，到最復(fù)雜的所有行為。
基于計算等價性原理的另一個推論就是「人可以理解宇宙」，或者是，漸進地理解宇宙。如果我們從計算的視角來定義「理解」，我們就能得到這個推論：我們定義A「理解」B，是A能夠在大腦，或者自身的某個系統(tǒng)之中，具象，或者抽象的重現(xiàn)出B。即A能模擬B、A能運行B。
我們說「我理解一個物理定律」，最基本的，就是能夠在大腦中通過物理圖像、公式，來描述某個規(guī)則。
如果計算等價性原理是錯的，那么相對簡單的大腦如何理解相對復(fù)雜的宇宙呢？而如果承認計算等價性原理，我們就可以說，大腦的復(fù)雜性是與宇宙相同的，唯一的限制是容量，但我們依舊可以用計算機來拓展它的理解力。
Wolfram曾在果殼的專訪[8]中說：「宇宙的本質(zhì)是計算」?？峙缕渖钜庖苍谟诖?。
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 : 指可計算的系統(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)，科普版見：不可解的物理學難題，源于數(shù)學核心的悖論
8 : 斯蒂芬·沃爾夫勒姆：宇宙的本質(zhì)是計算
