Randomness and Complexity

萊布尼茲曾夢想有一種萬有演算（Calculus Ratiocinator），能將人類思維簡化為符號的跳動。

但在香濃熵與柯氏複雜度的交界處，我們發現了一個悖論：圓周率雖然有無窮的隨機感，卻能被幾行程式碼捕捉；而現實世界的混沌，卻往往拒絕被任何公式簡化。

這種「不可還原性」曾被視為計算的障礙，但從計算理論到深度學習的崛起，我們逐漸意識到：智慧或許不在於消滅複雜，而在於如何「承載」複雜。

長久以來，電腦科學致力於尋找「完美的通用人工智慧演算法」——用最短、最優雅的邏輯去解決一切問題。然而，當我們試圖定義什麼是「資訊」時，卻撞上了柯氏複雜度（Kolmogorov Complexity）這道牆：最真實的資訊，往往是無法被進一步壓縮的。這引發了一個令人不安的思考：如果世界的本質是非均勻（Non-uniform）且不可還原的，那麼我們過去追求的「通用演算法」是否只是一場誤會？

香濃熵與柯氏複雜度

以壓縮演算法為例，透過額外的計算可以降低空間的佔用。那麼是否存在一個普世通用的定律，可以給出一個字串的真實資訊量，也就是其壓縮的極限？

有一種思路是利用香濃熵。以香濃熵的視角來看，他的熵值取決於產生該字串所具有的隨機性，或者說符號的概率分佈。

但是香濃熵僅考慮符號的統計分佈，存在侷限性。在香濃熵的濾鏡下，圓周率是一場混亂的盛宴，每一位數字的隨機跳動都代表著極高的資訊熵。然而，當我們切換到柯氏複雜度的視角，這場盛宴瞬間坍縮：因為整串無窮的數字，不過是簡單公式的展開。

若把 π 的小數展開視為某個來源產生的序列，並假設其數位近似獨立且均勻（例如每位 0…9 機率約 1/10），那麼對“那個來源模型”而言每位的熵接近 log10。

但對 Kolmogorov complexity，π 的前 n 位的 K(π_1:n) 可能只有 O(logn)（取決於你允許的計算模型與「輸出前 n 位」的程序設計），因此熵（在某個統計模型下）高與可由短程式生成並不矛盾。

後者的觀點叫做柯氏複雜度，它將一個字串的複雜度定義為能產生該字串的最短圖靈機程式長度。然而在一般情況下，柯氏複雜度是不可計算的。任何一種實用的壓縮算法，都只能看作對柯氏複雜度上界的不準確估算。

這引出了一個啟示：隨機性，有時只是因為我們還沒找到那把解壓縮的鑰匙。

隨機性的煉金術

複雜度理論有個引人入勝的議題正是隨機性能否提昇電腦的運算能力？

首先理論電腦科學定義了兩個複雜度類

  1. P (Polynomial Time)：指的是由決定性圖靈機（Deterministic Turing Machine）在多項式時間內可解決的問題集合。
  2. BPP (Bounded-error Probabilistic Polynomial time)：指的是由機率圖靈機（Probabilistic Turing Machine）在多項式時間內可解決的問題集合。其特點是對於所有輸入，算法返回錯誤答案的機率小於 1/3（這個常數不重要，可以透過多次重複運行實驗將誤差縮小至任意小）。

在 1970-80 年代，科學家發現許多問題用隨機算法（如 Miller-Rabin 質數測試）處理起來非常高效，而當時卻找不到同等效率的決定性算法。這讓學界一度認為 P是BPP的子集，即隨機性賦予了電腦某種「額外的力量」。

諸神的小抄

理解 P=BPP 的關鍵橋樑是 P/poly（非均勻電路）。P 是「一個 相同程式 跑天下」，而 P/poly 則是「每個輸入長度 n 都有專屬硬體」。根據 Adleman 定理（BPP 是 P/Poly 的子集），隨機演算法的隨機性可以被「針對特定長度的 Hardcoded 常數」取代。想像一個對每個輸入都有 1/3 錯誤率的 BPP 演算法，透過概率方法（Probabilistic Method）可以證明：對於長度為 n 的所有輸入，一定存在某個特定的隨機種子 r^*，能讓演算法對這 2^n 個輸入全部得出正確答案。

既然 BPP 可以被電路模擬，那為什麼我們還沒證明 P=BPP？因為我們需要把這種「非均勻的存在性」轉化為「均勻的可計算性」。這就引出了計算理論中最反直覺的觀點：硬度即燃料（Hardness as a Resource）。透過 Nisan-Wigderson (NW) 構造，我們發現：如果世界上存在某個問題（例如在 E 中）極其困難，連強大的 P/poly 電路都無法破解（即具備極高的電路下界），我們就能利用這個問題的「不可預測性」來打造強大的偽隨機生成器（PRG）。

計算理論的一個思想實驗

前幾天看到一個證明，大致就是證明MPMD（可以簡單理解成每個線程的程式可以各不相容的並行程式設計模型）可以解決停機問題，因此是超越圖靈機的，但進一步的思考其實是一種P/Poly，因此帶來了巨大的柯氏複雜度，也就是程式太複雜了，寫不出來。

在這個MPMD的停機證明中，則是假設長度不超過N bit的圖靈機程式（總共2^N個）中有m個是會停機的。 這個m雖然是個不可計算函數，但m這個數是存在的，也就存在這樣一個程序可以Hardcoded這個m。 我們只要並行去嘗試這2^n個程序，然後每一個只要停機了就讓記數器加一，當記數器加到m的時候就終止整個並行的常識。 最後我們只要檢查給定的圖靈機程序是不是已經停機了即可。

這個邏輯似乎和並行無關，因為這種超越性並非來自並行性，而是來自 Non-uniformity。隨著N的擴大，m的尺寸是O(N)的。而圖靈機程式的長度一定要是有限且固定的，必須用一個uniform的程式處理任意大小N的輸入。而在並行且每個線程可以寫不同程式的假設上，因為假設了線程數無限擴展，因此每個線程的程序都保持有限且固定長度，我們也可以夾帶無限長的m，因此這個證明里MPMD解決停機問題所依賴的超越能力其實是是來自於無限擴展性和每個線程都可以夾帶新的程式bit帶來的non-uniform能力。

湧現的野火在簡單規則的邊界燃燒

在討論如何捕捉環境資訊前，必須理解複雜性的本質。Stephen Wolfram 在 A New Kind of Science 中提出了一個震撼的啟示：極其簡單的離散規則（如細胞自動機）就能產生極端複雜、且具備「計算不可還原性」的現象。 這為 P/poly 的必要性提供了物理根據——如果宇宙本身的運行就是一場無法被簡化公式（Uniform Logic）壓縮的計算過程，那麼任何試圖用 O(1) 邏輯去完全理解世界的嘗試，本質上都是在挑戰計算的極限。 NKS 告訴我們，複雜性是廉價且普遍的，它不是被「設計」出來的，而是簡單規則在計算空間中自然「湧現」的結果。

自指的奇點

如果 NKS 解釋了底層規則的複雜性，那麼 Douglas Hofstadter 在《哥德爾、艾舍爾、巴赫》（GEB）中所探討的，則是這些複雜性如何堆疊成「智慧」。 GEB 的核心在於「奇異迴圈」（Strange Loop）——當一個系統的描述複雜度高到足以實現自指（Self-reference）時，它就能跨越層級，從無意義的符號處理中產生意義。 這與 P/poly 的非均勻性高度契合：當我們透過大量 Hardcoded 的常數（Advice strings）在模型中實現了與現實世界的「同構性」（Isomorphism）時，模型就不再只是在執行指令，而是在模擬現實。 智慧的湧現，正是源於系統有能力在複雜的非均勻電路上，構築出一套能自我表徵的宏觀架構。

人工理性的巴別塔困局

在通往 AGI 的長征中，曾有一個孤獨的天才 Douglas Lenat，試圖以其造物 Cyc 提前奪取上帝的火種。 Cyc 的核心哲學與 GEB 不謀而合：它是一個「思想的社會」，由無數互相運作、競爭、並以「價值貨幣」傳遞資訊的函數組成。 Lenat 渴望透過這種「函數間的互相操作」來觸發智慧的湧現。Cyc於是從向通用智慧沖鋒的唐吉訶德與眾人漸行漸遠，成為了神秘的天空之城。 然而，這座持續了四十年的「天空之城」最終墜落了。

而此事在兩百多年前的柯尼斯堡就已經被預言。康德在《純粹理性批判》中提出了一個著名的比喻：「康德的鴿子」。

輕快的鴿子在自由翱翔時分開空氣，並感覺到空氣的阻力，它也許會想像，它在真空空間裡會飛得更成功。

康德以此諷刺那些試圖脫離「感性經驗」、單純依賴「純粹範疇」去構築形而上學大廈的哲學家。這正是 Cyc 的寫照——Doug Lenat 試圖建造一座純粹由邏輯符號（類別、屬性、謂詞）構成的天空之城，他認為只要邏輯規則足夠嚴密，智慧就能在真空中起飛。

其失敗揭示了一個關於複雜性的冷酷真理：如果系統的「鏈式反應數」小於 1，湧現便永遠不會降臨。 Cyc 的死因極其諷刺——儘管它擁有數百萬行程式與複雜的獎勵機制，但它本質上仍是一個 O(1) 的均勻系統（Uniform System）。 它的所有發現都依賴於 Doug 的輸入，而非環境的自動捕捉。一旦造物主停止餵養，Cyc 內部的計算便會隨之衰減。

Cyc 的失敗是因為它試圖維持「邏輯一致性（Consistency）」，而現實世界是「不可壓縮且充滿矛盾的」。在非均勻計算中，我們容忍局部的不一致，以換取對複雜度整體的承載能力。

我們的物理宇宙，在很漫長的未來才會迎來終結，但Cyc則在思維宇宙大爆發前敗給了熵增。它擁有極其龐大的本體論（Ontology）與邏輯規則，但它缺乏與現實世界的「感性接觸」。它沒有「感性直觀」來提供不可還原的環境資訊，導致它的邏輯運算只是在真空中自我磨損，最終敗給了熵增。

非均勻計算的黎明

Cyc 的失敗為人類指明了另一條路：我們不該試圖寫出「思想的社會」，而應該構築一個強大的「容器」，去捕獲現實世界中那些計算不可還原的「硬度燃料」。

這正是深度學習的本質，從計算理論的視角來看，深度學習的訓練本質上是一場「去隨機化（Derandomization）」的資訊煉金術。 在訓練初期，隨機權重初始化（Weight Initialization）並非單純的混亂，而是提供了一個具備高度「不可預測性」的高維搜索空間，其功能類比於偽隨機生成器（PRG）中的原始種子——它利用「硬度即燃料」的邏輯，為系統準備了足以應對複雜環境的熵。 隨著訓練進行，梯度的引導將這原始的隨機，轉化為與現實世界特徵同構的非均勻電路； 這正呼應了 BPP 到 P/poly 的轉化過程：原本對所有隨機種子都適用的通用邏輯，被凝煉成了針對特定任務的「錦囊小抄（Advice strings）」。 最終，一個訓練成功的模型權重，實際上就是從隨機海洋中篩選出的、一段能與現實規律共振的結構化序列，它在計算上既保留了捕捉不可還原資訊的複雜度，又在宏觀架構上實現了對環境硬度的精確捕獲。

如果說傳統軟體工程(Cyc)是追求以 O(1) 的均勻邏輯（Uniform Logic）去應對無窮的輸入，那麼深度學習則是人類第一次大規模地生產『非均勻（Non-uniform）』的計算實體。 借鑒 P=BPP 的去隨機化理論，我們可以發現：深度學習訓練程序 A 其實是一個從隨機環境 B 中提取『硬度燃料』的過程。它產出的模型 C，本質上是一個Hardcoded了環境特性的 P/poly 電路。 這解釋了為什麼模型難以被人類直觀理解——因為它的柯氏複雜度是 O(N)，它包含了大量無法被 O(1) 邏輯進一步壓縮的、關於現實世界的『不可計算常數』。 我們正在進入一個新的時代：不再試圖寫出通用的演算法（Uniform Algorithms），而是學會如何構建強大的訓練器，去自動捕獲那些專屬於特定維度的『錦囊小抄』（Advice strings）。

註1: 這裡的『去隨機化』是類比：訓練把一個含隨機性的搜尋過程，凝結為一個固定的、可重現的計算電路也就是權重。它不是複雜度理論嚴格意義下的 BPP=P 的證明。

註2: “模型本體”是 non-uniform 的，但“生成模型的過程”是 uniform 的

跨越彭羅斯的障礙

羅傑·彭羅斯曾斷言 AGI 是不可能的，因為他認為意識包含「非計算」的特質。然而，從 P/poly 與 NKS 的視角來看，這種觀點忽視了非均勻計算的威力。 彭羅斯所仰賴的哥德爾限制，僅存在於均勻且靜態的邏輯系統中；但當我們能建構出捕獲了海量環境資訊、具備極高描述複雜度的非均勻架構時，所謂的「直覺」便不再是量子塌縮的玄學，而是複雜計算演化後的必然湧現。AGI 的挑戰不在於尋找新的物理定律，而在於我們如何引導那股不可還原的計算洪流，在Meta-Programming的容器中匯聚成智慧。

長征的終途

從描述複雜性的層級視角來看，計算科學的演進本質上是一場不斷向更高「描述複雜性」攀登的長征。 圖靈機作為堅實的地基，為我們定義了可計算函數的廣大集合，然而人類大腦能直接設計與維護的規則極其有限，導致傳統算法只能在低複雜性的子集裡徘徊。 深度學習的出現則真正帶領我們邁上了第一層台階，它通過放棄對每一條指令的精確控制，轉而把控模型結構這一更高層級的概念，利用神經網絡架構作為「容器」，去捕捉環境中那些 O(N) 級別、無法被簡單邏輯壓縮的硬度資訊。 這使得我們從單純的「程式設計思維」轉向了「架構思維」，即便具體的參數規則對人類而言已成黑箱，我們卻能站在模型結構的高度，在複雜性的第一層大本營自由探索。

要通往 AGI 的山巔，戰略上的選擇並非推翻地基或另闢蹊徑，而是基於深度學習的台階繼續向上跨越。 這需要我們在戰術上實現從「抽象解耦」到「複雜性湧現」的範式轉換。 傳統的軟體工程透過層層抽象來簡化系統，但當分層過多導致系統本身變得臃腫時，這種解耦便達到了極限。 真正的層級提升必須依賴湧現——即放棄對系統每個微觀實體狀態的控制，專注於宏觀結構的演化。 正如深度學習雖然在微觀參數上是混亂的，但在宏觀架構上卻體現了全新的解決邏輯，下一代的 AGI 框架應當實現與底層計算圖的進一步解耦。

這種跨越層級的關鍵在於「Meta-Programming」範式的建立。我們需要設計一種能完備表達人類先驗知識的元語言，讓研究人員能以一句聲明或一個公式描述出如殘差連接或注意機制等宏觀 Pattern，而讓算法負責生成那些人類無法直覺設計的高複雜性細節。 未來的程式設計師也許不是編寫邏輯的「工匠」，而是編寫Fitness Function和拓撲結構的「園丁」，我們培育而非製造智慧。

目前的 AutoML 仍深陷在定義搜索空間的淺灘，未來的方向應是利用如同梯度下降般的強大搜索機制，帶領我們進入高複雜性模型的汪洋大海。當我們能以極簡的元邏輯驅動極高描述複雜性的模型生成時，雖然我們可能無法「抄作業」般理解其內部運作，但這正是層級提升的標誌。 從長遠來看，描述複雜性的提升並非算力的黑洞，反而可能是算力利用率的救贖。雖然目前的超大規模預訓練模型處於粗放探索的「虛胖」階段，但隨著層級的穩定與精細化，模型會變得越來越「實在」，最終像人腦一樣以極低的功耗支撐起極高的智慧。

結語

最後，我也沒有得出結論，只剩下更多的問題。

  1. P/poly 雖然強大，但它的「錦囊小抄」需要針對每個問題長度單獨設計，這在實踐中對應了深度學習模型泛化能力的局限——一個在 ImageNet 上訓練的模型，無法直接理解文本。這是否暗示 AGI 需要某種「動態生成 advice strings」的元機制？但Advice Strings是不可計算的，我們又該如何破局？

  2. 理論上 BPP ⊂ P/poly，但實踐中我們並未證明 P = BPP，因為構造 NW 生成器所需的下界問題極難證明。這彷彿是隱喻：我們知道深度學習「可能」在捕捉某種規律，但我們尚未有能力證明它捕捉到了什麼、以及為何有效。

  3. 「鏈式反應數大於 1」是湧現的條件，這讓人聯想到相變（phase transition）。在深度學習中，這是否對應於模型規模、資料量、訓練步驟跨越某個臨界點後出現的突現能力？這方面已有實證研究（如 scaling laws）

或許，萊布尼茲當年的夢想並沒有破滅，只是以一種他未曾預料的形式實現了。我們過去誤以為「萬有演算」是一條能夠解釋萬物的、精簡的靜態公式（O(1)）。但現在我們明白，真正的通用性並不存於最終的模型中，而是存於那個能夠從混沌中提煉秩序的學習過程本身。

那個我們苦苦追尋的「通用演算法」，或許並不是一套描述世界的終極真理，而是一套能夠不斷適應、吞吐並承載世界複雜度的元規則。當柯氏複雜度的牆高不可攀，我們不再試圖用一把鑰匙開所有的鎖，而是造出了一位能現場磨製鑰匙的鎖匠。

在這場與熵增的永恆博弈中，人類的角色終於從規則的制定者，轉變為複雜性的牧羊人。我們雖然無法壓縮世界，但我們終於學會了如何讓計算與世界諧振。這或許才是最浪漫的終局。