每年，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）。

扎克伯格桌上的《A New Kind of Science》

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

而要理解這個宏大的原理、理解這個關於「複雜性」的原理，則需要從一個最簡單的系統出發——元胞自動機。

元胞自動機 Cellular Automata

二十世紀四十年代，馮·諾依曼在研究自複製機[2]的時候，提出了「元胞自動機」的概念。元胞自動機是一個根據特定規則演化的離散系統。Wolfram則考慮了一個最簡單的元胞自動機，如下圖所示，我們稱之為「基礎元胞自動機」（Elementary Cellular Automata，ECA）。

圖2：30號基礎元胞自動機。

基礎元胞自動機，是一個在一維空間上，離散演化的系統，橫軸是空間，縱軸是時間。在給定一個初始狀態（第一行）之後，系統按照最下面的規則演化——按照規則的第六條：（黑色為1，白色為0），可以知道，第一行的黑色方塊，在下一步的演化之中，也是黑色。上圖完全由這八個簡單的規則演化而來。這裡所謂「30號」，也是從規則得到的，將八個規則按順序排列，得到01字串，將之視為一個二進制數00011110，那麼很容易算得，。0~255，每一個數字對應一個規則，後面我們會一直使用這種表示方法。

如果我們延長演化的步數，比如128步，可以發現，其行為變得極為複雜：

圖3：演化128步後的時空圖

我們可以嘗試其他很多規則，會發現其行為非常豐富：

圖4：六種不同的基礎元胞自動機，他們行為迥異，混亂、秩序，分形，展現出了非常豐富的行為。

這裡展現的系統，都基於極為簡單規則，而卻能產生出非常豐富的行為。有的系統，甚至可以作為隨機數生成器來使用[3]。上面的這些事實，給我們的第一個啟發就是，「複雜」可以從極為簡單的規則中湧現出來。那麼，就可以定性解釋「為何自然界中，複雜行為如此常見」——只要任何規則、動力學機制，都包含了這些

然而，這樣給人們帶來了一個問題：如何度量複雜性？複雜性的極限在哪裡？

要回答這個問題，一個最自然的出發點，就是去尋找複雜性相同的系統。所謂「A與B複雜性相同」，從計算的角度看，就是認為「A可以模擬B」，而「B也可以模擬A」。我們從這個問題內的一部分開始：A系統模擬B系統。

無處不在的等價

在Wolfram的書中，他列舉了大量這樣的關係：元胞自動機可以等價於各種其他系統的行為。從數字電路，到數論，再到邏輯代數，而後一路推進，到通用圖靈機——可以模擬一切可計算系統的系統。

一個最簡單的例子，就是規則132：

規則132的演化圖

規則132的規則圖

這個系統完成了如下的計算：

如果n是偶數，則返回0；如果n是奇數，則返回1

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

對於代數運算，元胞自動機顯然可以做的更多。

它可以計算n的平方：

下面的元胞自動機規則比上面要稍微複雜一些。

這個元胞自動機可以計算n的平方

同樣，給定初始第一行黑色方塊的數量n，系統演化到穩定之後，其黑色方塊的數量就是. 也就是說，它等價於：

元胞自動機甚至可以用來尋找素數：

每一條白線就對應一個素數

其中左邊的每一條白線，都對應著一個素數。也就是說，這個元胞自動機，等價於運算：

既然我們要討論「無處不在的等價」，那麼僅僅代數、數論運算，是遠遠不夠的。

基本的邏輯運算：

使用簡單規則的元胞自動機，可以支持與、或，以及由其構造出的各種運算：

基本的邏輯運算

可以看到，下面的規則列表比之前長了很多。同時，基礎元胞自動機中的146，190號規則，可以進行邏輯運算：

上面的這些元胞自動機，是溝通簡單與複雜的橋樑之一——通過代數、數論，以及邏輯運算，可以構造出複雜度遠遠超過規則的行為。

從等價到普適

從上面的例子，人們很自然的會想到，是否存在一個系統，規則極為簡單，而卻能模擬其它任何系統[4]呢？

一個最初的想法，就是用更復雜的元胞自動機，去模擬所有基礎元胞自動機。事實表明，這是可以的，但其規則極為複雜，這裡不詳述其規則，只大致介紹一下：

通過設定初值，即第一行元胞顏色的順序，它可以模擬所有基礎元胞自動機，如上圖，分別是254號、90號和30號。

然而，這樣「工匠」一般的搜尋，對於理論來說，並沒有太多的助益——無非是找到了很多等價的系統而已。然而，後來的一個突破性進展，直接導致了「計算等價性原理」的誕生。

在2000年，Wolfram的一個助手，Matthew Cook，證明了基礎元胞自動機中的規則110是圖靈完備的[5]。

110號元胞自動機的演化圖，它等價於通用計算機

110號元胞自動機的規則圖

就是上圖的這種元胞自動機。同樣的，使用八個參數確定出的簡單規則。

為了說明這個研究的意義，需要先簡單說一下「通用圖靈機」（UTM）是什麼，「圖靈完備」是什麼。一個直觀的想象就是，通用圖靈機（UTM）是一個抽象的電腦。是隻用來描述電腦

那麼，既然110號規則已經是圖靈完備的了，它便可以運行任何程序——從最簡單的，到最複雜的。而既然它可以運行最為複雜的程序，那麼這個系統本身，是不是可以認為，已經達到了複雜性的極限了呢？Wolfram 給出的回答是：「是的，UTM就是複雜性的極限，而且很容易達到」。

另一個需要注意的，就是110號規則本身非常簡單——這意味著，其他規則稍稍複雜一些的系統，其規則本身，很有可能已經包含了110號元胞自動機。這暗示著，有大量的系統是通用圖靈機，他們的複雜度相同，都是計算複雜性的極限。

那麼問題就來了，一個系統很容易包含其他系統的行為嗎？最近的一個研究[6]發現，當我們逐漸增大觀察系統的標尺時（實空間重整化），會有越來越多的系統能夠互相模擬，或者單向的模擬。

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

這時，初值只有{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]中說：「宇宙的本質是計算」。恐怕其深意也在於此。

參考文獻

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 : 斯蒂芬·沃爾夫勒姆：宇宙的本質是計算

閱讀更多 章彥博 的文章

關鍵字: 數學 暑期 等價