這篇文章是與 Iliad 合作撰寫的，旨在服務於 Iliad 的長期目標之一：理解學習機器的「簡單性偏誤」（simplicity bias）。

所羅門諾夫歸納法（Solomonoff induction）是一個通用的理論理想，用於預測由可計算過程生成的序列。它主張，為了預測我們世界的延續，我們應該根據假設的簡單性（「奧卡姆剃刀」）對其進行加權，並使用貝氏推理（Bayesian reasoning）來更新權重。

在本文中，我將從技術層面介紹所羅門諾夫歸納法，希望能比你在其他地方看到的介紹更優雅且令人滿意。特別是，本介紹避開了柯氏複雜度（Kolmogorov complexity）：我們不使用假設的所羅門諾夫先驗概率（即其最短編碼長度的負二次方，亦即柯氏複雜度）來進行預測，而是直接使用「假設是從隨機均勻採樣的代碼中採樣得出」的先驗概率。這與 Nate Soares 之前簡述的替代複雜度（alt-complexity）密切相關。這種方法能得出比典型論述更優雅且更容易證明的結果。然而，由於僅改變了假設的先驗分佈，本介紹仍與其他論述保持兼容，對廣大讀者應具有廣泛價值。

稍後我們將看到，與基於柯氏複雜度的方法相比，這種選擇在數學上既有優點也有缺點，而後者可能是構建更多理論的更強大基礎。儘管有這些缺點，我希望這篇介紹在哲學上能令人滿意，觸及諸如「為什麼我們首先應該預期世界是可學習或可預測的？」、「什麼是普遍良好的預測方式？」等問題，以及與奧卡姆剃刀的聯繫，以及為什麼在預測世界時應該偏好簡單的假設。在最後的常見問題（FAQ）中，我將探討幾個預期的問題，包括簡要說明該理論如何與神經網絡相關聯。

受眾： 我盡量不嚴格假設讀者具備太多關於圖靈機或相關概念的背景知識，但預先接觸過這些概念仍會非常有幫助。一定程度的數學或科學素養或許可以彌補對這些主題接觸的不足。

致謝： 本文主要受益於與 Alexander Oldenziel 的討論，且起因於他對學習到的神經網絡函數是否可能基於與算法信息論（AIT）的類比而具有簡單性的詢問。這促使我想要更仔細地思考 AIT 本身的「退化優先」（degeneracy-first）視角，本文便由此產生。我也感謝 Cole Wyeth 的討論以及他對早期草案的反饋，這促成了一些修改；他還向我解釋了為什麼所羅門諾夫先驗在所有下半可計算先驗中給出了最優預測界的論據。感謝 Matt Dellago 對本文內容的討論，以及 CEEALAR 在我完成寫作期間提供的款待。

導論

如果我們對世界進行一系列觀察，例如一組數字序列：

1, 1, 2, 3, 5, 8, 13, …

或是物理測量序列，我們通常能夠以一種與現實中「真實延續」相吻合的方式來延續該序列。這在現實世界的許多領域似乎都廣泛有效，這意味著世界是可學習的——我們可以從過去的經驗中學習以預測未來。

這是為什麼呢？這個問題困擾了人類數千年。例如，塞克斯圖斯·恩比里柯（Sextus Empiricus）表示，任何從有限數據推導出的規則都可能被更多數據推翻，而且不可能考慮到所有數據：

「當他們提議通過歸納法從特殊事物建立普遍規律時，他們將通過審查全部或部分特殊事物來實現。但如果他們只審查部分，歸納將是不安全的，因為歸納中省略的某些特殊事物可能會違反普遍規律；而如果他們要審查全部，他們將是在徒勞地做不可能的事，因為特殊事物是無限且不確定的。」

—— 塞克斯圖斯·恩比里柯 (160-210)

勒內·笛卡兒（René Descartes）注意到我們的心靈是如此容易出錯，以至於我們甚至無法確定自己是否清醒：

「有多少次，我在夜裡睡著時，確信自己正經歷著這些熟悉的事件——我穿著睡袍坐在火爐旁——而事實上我卻赤身裸體地躺在床上！然而此刻，當我看著這張紙時，我的眼睛無疑是清醒的；我搖搖頭，它並沒有睡著；當我伸出手並感覺到它時，我是刻意為之，且知道自己在做什麼。這一切對於睡著的人來說不會如此清晰。的確！彷彿我不記得其他時候我也曾被同樣的想法欺騙過！當我更仔細地思考這一點時，我清楚地看到，從來沒有任何確定的跡象可以區分清醒與睡眠。結果是我開始感到眩暈，而這種感覺本身只會強化我可能正在睡覺的念頭。」

—— 勒內·笛卡兒 (1596-1650)

在接下來的段落中，大衛·休謨（David Hume）似乎暗示，雖然我們可以通過類比過去的模式來對因果關係做出未來的推論，但在自然界本身中找不到任何可以證明這樣做是合理的原則：

「我們關於事實的所有推理都建立在某種類比之上，這使我們期望從任何原因中得到與我們觀察到的類似原因所產生的相同事件。[...] 動物的這種推論不可能建立在任何論證或推理過程之上，藉此他得出結論：相似的事件必須跟隨相似的對象，且自然的進程在其運作中將始終是有規律的。因為如果現實中存在任何性質的論證，它們對於如此不完善的理解力來說肯定過於深奧；因為即使是哲學天才也需要極大的細心和注意力才能發現和觀察它們。」

—— 大衛·休謨 (1711-1776)

類似的推理也體現在無免費午餐定理中，該定理大致指出，從先驗角度看，沒有任何學習算法應該優於其他算法。

我們得出的結論是：如果不對世界做任何假設，學習和預測確實應該是不可能的。如果世界真的是（均勻）隨機的，那麼任何利用過去數據預測未來的方法都注定失敗。那麼，為什麼學習是可能的呢？

一個非正式的答案是奧卡姆剃刀（Occam's razor），它有各種表述，核心是：在所有與我們的觀察相符的解釋中，我們應該選擇假設最少的那一個。通常歸功於奧卡姆的兩句話如下：

「若無必要，勿增實體。」

「能以較少者完成的事，若以較多者去完成則是徒勞。」

—— 奧卡姆的威廉 (1287-1347)

奧卡姆剃刀是一個有用的起點，但它不夠正式。此外，如果能從某個最小假設中證明奧卡姆剃刀的合理性，而不是僅僅在推理中「假設」我們應該關注簡單的假設，那將會更好。該如何做到這一點呢？

在本文中，我從一個最小假設出發來推導答案：我們的世界是被計算出來的。在不知道它是被什麼計算出來的情況下，我們假設我們是通過在通用圖靈機上運行一個均勻隨機採樣的程序代碼而生成的（章節連結）。

這個假設的一個結果是，我們也可以將我們的世界視為通過一個兩階段過程採樣得出的：首先從先驗分佈中採樣一個下半可計算的（可能是概率性的）宇宙，然後從該宇宙生成我們的歷史。事實證明，宇宙的先驗分佈——我稱之為先驗之先驗（a priori prior）——將自動內建簡單性加權，從而證明了奧卡姆剃刀的合理性（章節連結）。

將這種兩階段分佈重新用於進行預測，便引出了所羅門諾夫歸納法，無論我們宇宙背後的真實計算是什麼，它都具有卓越的預測能力。也就是說，即使我們真實宇宙背後的程序代碼實際上不是隨機採樣的，而是為了讓預測任務變得困難而對抗性地選擇的，只要觀察到的歷史足夠長，我們最終也會收斂到完美的預測（章節連結）。

接著，我將討論我選擇「先驗之先驗」的缺點。特別是，權重可能不是下半可計算的，且與基於柯氏複雜度的經典所羅門諾夫先驗不同，「先驗之先驗」在通用圖靈機變更時，在常數倍數範圍內不具備不變性。此外，所羅門諾夫先驗滿足序列預測的最優性，而「先驗之先驗」則沒有類似形式的最優性。這也意味著我選擇的先驗（可以被視為基於假設的概率或退化程度）與基於描述長度的方法有本質上的不同（章節連結）。

這表明「描述長度等於退化程度」這一準則在算法信息論中並非普適。與此相關，我在腳註中討論了與 Nate Soares 的替代複雜度的關係，並將解釋為什麼該貼文下的許多評論者關於 K 複雜度和替代複雜度在常數倍數內完全相同的看法可能是錯誤的。儘管存在這些問題，我確實認為我選擇的先驗在先驗上更容易證明其合理性，依賴的選擇更少，並且使某些結果顯得更優雅。

最後我將進行總結，並在 FAQ 中預測一些問題，重點簡要討論：在觀察者僅能觀察到宇宙部分歷史的情況下如何思考所羅門諾夫歸納法、其實際用途、所羅門諾夫歸納法作為理解神經網絡的理論理想的潛在適用性、所羅門諾夫歸納法是否可被視為「萬有理論」，以及編碼長度對所使用的圖靈機模型的敏感性。這些回答都是初步的，關於這些問題還有更多內容可以探討或研究。

關於由隨機電腦程序生成

觀察我們的世界，未來似乎是由過去通過精確的規則決定的。我們通過一個最小假設來捕捉這一點：我們的世界是被計算出來的。在沒有關於生成我們的程序的先驗知識的情況下，我們簡單地假設我們的歷史是通過採樣一個均勻隨機的電腦程序，並將其輸入到一個輸出序列的通用編程語言中而產生的。

在本節中，我將正式定義這意味著什麼。令 $B={0,1}$ 為我們的位元字母表。$B^* = \cup_{n \in \mathbb{N}_{\ge 0}} B^n$ 是任意有限長度二進位字串的集合（其中明確允許長度為 0 的字串 $\epsilon$！）。$B^\infty = {0,1}^\infty$ 是無限二進位序列的集合。而 $B^{\le \infty} = B^* \cup B^\infty$ 是有限或無限二進位序列的集合。對於兩個序列 $x \in B^*$ 和 $y \in B^{\le \infty}$，我們將它們的連接記為 $xy$。此時稱 $x$ 是 $xy$ 的前綴，記作 $x \preceq xy$。

單調圖靈機

我們如何捕捉「被計算」這一點？一個想法是假設我們是由一個程序逐「幀」生成的，且該程序永遠不會更改過去的幀。這引出了 Li 和 Vitányi 定義 4.5.3 中的單調圖靈機（monotone Turing machine） $T$ 的形式化。^([1]) 正式地說，單調圖靈機是一個可計算函數 $T: B^* \to B^{\le \infty}$，具有單調性：對於所有 $p, q \in B^*$ 且 $p \preceq q$，我們有 $T(p) \preceq T(q)$。^([2]) 這裡有很多內容需要解析，我希望以下的半正式解釋能提供足夠的直覺來閱讀本文的其餘部分：

• 輸入 $p \in B^*$ 可以解釋為以二進位代碼編寫的程序指令。
• 輸出 $T(p) \in B^{\le \infty}$ 是（可能是無限的）歷史；想像一下我們宇宙歷史的二進位編碼。因此，每個代碼 $p$ 都包含計算歷史 $T(p)$ 的指令。
• 你應該將 $T$ 想像成一種（可能是非通用的）編程語言，它將代碼 $p$ 翻譯成歷史 $T(p)$。
• 正式地說，$T: B^* \to B^{\le \infty}$ 是可計算的，僅意味著存在直覺意義上的「算法」，可以為給定的代碼計算出歷史。這由 丘奇-圖靈論題（Church-Turing thesis） 證明其合理性，這使我們能夠避開圖靈機的精確形式。
• 單調性正式定義為對於所有代碼 $p, q$ 且 $p \preceq q$，有 $T(p) \preceq T(q)$。直覺上，$T$ 從左到右讀取輸入代碼，並可能在此過程中已經寫入（任意數量的）輸出位元。早期的位元永遠不會被擦除。輸出只是通過連接更多位元來「單調增加」。
• 值得注意的是，即使輸入 $p$ 是有限的，$T$ 也有可能產生無限的輸出 $T(p)$。直覺上，當 $T$ 進入一個「循環」，根據先前的輸出歷史遞歸地應用相同的規則來產生下一個輸出位元時，就會發生這種情況。這類似於我們的物理歷史是由穩定的物理定律生成的，這些定律在給定現狀的條件下「循環」運行；物理定律本身從不改變。
• 如果確實發生 $T(p)$ 是無限輸出的情況，那麼任何進一步的位元都永遠不會被讀取，因此對於所有擴展 $q \in B^*$，都有 $T(p) = T(pq)$。
• $T(p)$ 可能是有限的，但對於所有 $q \in B^*$ 仍有 $T(p) = T(pq)$。直覺上，如果所有進一步的位元都被視為「死代碼」或不改變輸出的「註釋」，就會發生這種情況。

通用單調圖靈機

並非所有的單調圖靈機 $T$ 都同樣有趣。例如，想像一台機器 $T$ 對於任何輸入都只輸出空序列：這滿足上述所有屬性，但非常無聊。

另一個極端是通用單調圖靈機，它可以模擬所有其他機器。它通過處理特定格式的代碼來實現這一點：代碼首先使用二進位代碼 $p$ 描述一個任意的單調圖靈機，隨後是該機器的輸入 $q$。一個棘手的細節是，我們不能簡單地將 $p$ 和 $q$ 連接成 $pq$，因為那樣我們可能會忘記 $p$ 的描述在哪裡結束以及輸入 $q$ 從哪裡開始。

一個解決方案是對描述 $p \in B^*$ 使用以下前綴無關（prefix-free）編碼：

$$p' := 1^{l(bin(l(p)))} 0 bin(l(p)) p \in B^*$$

讓我們解析一下：$l(p)$ 是 $p$ 的長度。對於自然數 $n$，$bin(n)$ 是將 $n$ 編碼為二進位序列，通常按長度然後按字典序排列。$p'$ 首先包含一串 1，後跟一個 0。1 的數量正是 $bin(l(p))$ 的長度。讀完這些後，我們就知道接下來有多少位元編碼了 $l(p)$。讀完那些位元後，我們就知道 $p$ 的長度，因此再讀取這麼多位元後，我們就知道 $p$。因此，從算法上講，可以將 $p'q$ 形式的二進位序列分解為 $p$ 和 $q$，因為 $p'$ 本身會告訴你 $p$ 何時結束。

那麼，通用單調圖靈機 $U: B^* \to B^{\le \infty}$ 僅對 $p'q$ 形式的輸入產生非平凡的輸出。此外，對於每個 $p \in B^$，$T_p: q \mapsto T_p(q) := U(p'q)$ 本身就是一個單調圖靈機，且每個單調圖靈機 $T$ 都可以表示為 $T = T_p$（對於至少一個 $p \in B^$）。請注意，$U$ 在讀取 $q$ 之前永遠不會產生輸出位元，因為 $p'$ 僅編碼了一個單調圖靈機 $T$。因此，對於 $p'$ 的任何前綴 $r$，$U(r)$ 都只是空字串。

這是一個很好的定義，但這樣的通用機器存在嗎？答案是肯定的，這可以通過以可計算的方式枚舉單調圖靈機集來證明，Li 和 Vitányi ^([1]) 在定義 4.5.5 之前指出這「顯然」是可能的——但沒有給出證明。直覺上，通過思考通用編程語言，這是可以相信的：任何「單調圖靈機」都可以由任何通用編程語言（如 Python）中的有限代碼實現。

在本文的其餘部分，我固定使用一個通用單調圖靈機 $U$。在後面的章節中，我們將看到該理論對這台機器的選擇相當敏感，但目前我們暫不擔心這一點。

通用分佈

單調圖靈機 $T: B^* \to B^{\le \infty}$ 誘導了另一個函數（沿用相同符號）$T: B^\infty \to B^{\le \infty}$，其在無限輸入上的輸出被定義為有限前綴輸出的極限：^([3])

$$\forall s \in B^\infty: T(s) := \lim_{p \in B^*, p \preceq s} T(p)$$

現在，令 $P_u$ 為 $B^\infty$ 上的均勻分佈，它每次採樣一個位元，每個位元為 0 或 1 的概率各為 50%。令 $s \in B^\infty$ 是從 $P_u$ 採樣的隨機輸入，令 $x = U(s) \in B^{\le \infty}$ 為其輸出（可能是無限的）。對於有限的 $x \in B^*$，令 $M(x)$ 為歷史以 $x$ 開始的相應概率。正式定義如下：

定義 1（通用先驗分佈）。令 $U$ 為通用單調圖靈機，$P_u$ 為無限二進位代碼上的均勻分佈。歷史以 $x \in B^$ 開始的通用先驗概率定義為：*

$$M(x) := P_u({s \in B^\infty \mid x \preceq U(s)})$$

我邀請你停下來思考一下，與我在引言中強調的歷史困惑相比，這是一個多麼深刻的視角轉變：當錯誤地假設我們的歷史 $x$ 是均勻採樣時，我們無法預測未來，正如恩比里柯、笛卡兒和休謨所表達的懷疑觀點所表明的那樣。然而，通用先驗分佈 $M$ 並不假設歷史是均勻採樣的。相反，它假設代碼是均勻採樣的，歷史是通過固定的、確定的通用單調圖靈機 $U$ 從該代碼生成的。換句話說，我們認為我們的宇宙具有均勻採樣的描述而非歷史。

我們是否應該預期從 $M$ 採樣的歷史中存在任何規律性？如果是這樣，這種規律性能否為我們提供關於如何在我們實際的宇宙中預測序列延續的啟示？這些問題將在接下來的兩節中得到回答。

M 是一個通用混合分佈

我們現在陳述並證明通用分佈 $M$ 的一個等效描述，這將顯示 $M$ 具有某種簡單性加權。直覺上，從 $M$ 採樣歷史就像是你先以符合奧卡姆剃刀的方式採樣「概率物理定律」，然後使用該定律來採樣歷史。

下半可計算半測度

我們通過「半測度」（semimeasure）的概念來正式化「概率物理定律」：

定義 2（（下半可計算）半測度）。函數 $\nu: B^ \to [0,1]$ 如果滿足 $\nu(\epsilon)=1$^([4]) 且對於所有 $x \in B^$ 有 $\nu(x) \ge \nu(x0) + \nu(x1)$，則稱為半測度。如果 $\nu$ 可以從下方進行可計算的逼近，則稱為下半可計算；這意味著存在一個算法，在輸入 $x$ 時，能從下方產生 $\nu(x)$ 的漸進逼近值。從現在起，我將「下半可計算半測度」縮寫為 LSCSM。

對於一個 LSCSM $\nu$，$\nu(x)$ 被解釋為在 $\nu$ 下，無限序列以 $x$ 開始的概率。我們可以有 $\nu(x) > \nu(x0) + \nu(x1)$，因為序列在以 $x$ 開始後可能不再繼續。這類似於宇宙可能在任何時刻結束的可能性。

順便提一下，LSCSM 也包括確定性序列：令 $s \in B^\infty$ 是一個可以由電腦程序生成的固定序列。定義當 $x$ 是 $s$ 的前綴時 $\nu(x)=1$，否則 $\nu(x)=0$。那麼對於給定的 $x$，我們可以通過計算 $s$ 並判斷 $x$ 是否為其前綴來計算 $\nu(x)$。這表明 $\nu$ 是一個生成序列 $s$ 的 LSCSM。

我們如何獲得 LSCSM？首先，我們已經知道一個例子：$M$ 是一個半測度，因為

$$M(\epsilon) = P_u({s \mid \epsilon \preceq U(s)}) = P(B^\infty) = 1$$

且對於每個 $x \in B^*$：

$${s \mid x \preceq U(s)} = {s \mid x0 \preceq U(s)} \dot{\cup} {s \mid x1 \preceq U(s)} \dot{\cup} {s \mid x = U(s)}$$

導致 $M(x) \ge M(x0) + M(x1)$。$M$ 也是下半可計算的。事實上，要從下方逼近 $M(x)$，只需枚舉所有有限二進位序列 $p$，並行計算所有 $p$ 的 $U(p)$，並記錄是否 $x \preceq U(p)$。如果是這種情況，那麼對於 $p$ 的所有無限擴展 $s$，我們都有 $x \preceq U(s)$，它們加在一起的概率為 $2^{-l(p)}$，其中 $l(p)$ 是 $p$ 的長度。因此，我們可以將 $2^{-l(p)}$ 加入我們對 $M(x)$ 的估計中，然後在算法過程中跳過 $p$ 的任何擴展。隨著過程進行，估計值會逐漸逼近 $M(x)$，因為對於每個滿足 $x \preceq U(s)$ 的 $s$，都存在一個有限前綴 $p \preceq s$ 滿足 $x \preceq U(p)$，這意味著我們最終會在逼近過程中找到該貢獻。

還有其他獲得 LSCSM 的方法嗎？你可能已經注意到，我在上面的解釋中沒有使用 $U$ 的通用性。換句話說，每個單調圖靈機 $T$ 通過輸入均勻隨機噪聲都會產生一個 LSCSM $\nu_T$：

$$\nu_T(x) := P_u({s \in B^\infty \mid x \preceq T(s)})$$

而這就是全部：所有的 LSCSM 都是以這種方式從單調圖靈機產生的，參見 Li 和 Vitányi ^([1]) 的定理 4.5.2。^([5])

混合等效性

現在，對於 $p \in B^$，定義函數 $T_p: B^ \to B^{\le \infty}$ 為

$$T_p(q) := U(p'q)$$

它本身也是一個單調圖靈機。定義 LSCSM $\nu_p := \nu_{T_p}$。

定義 3（先驗之先驗）。*對於任何 LSCSM $\nu$，**先驗之先驗（a priori prior）*由下式給出：

$$P_{ap}(\nu) := \sum_{p \in B^*: \nu_p = \nu} 2^{-l(p')}$$

這是一個均勻隨機無限序列 $s \in B^\infty$ 以編碼 $p'$ 開始，且該編碼產生 LSCSM $\nu_p = \nu$ 的概率。^([6])

我之所以稱之為「先驗之先驗」，是因為它只是從我們的定義中自然產生的，沒有進一步的假設，這使其區別於我稍後將研究的基於柯氏複雜度的所羅門諾夫先驗（章節連結）。

最後，令 $\mathcal{M}_{sol}$ 為所有 LSCSM 的集合，其中「sol」是所羅門諾夫的縮寫。我們得到：

定理 4（混合等效性）。通用分佈 $M$ 是所有 LSCSM 的通用混合，其權重為 $P_{ap}(\nu)$：

$$M(x) = \sum_{\nu \in \mathcal{M}{sol}} P{ap}(\nu) \nu(x)$$

證明。 由於 $U$ 僅對 $p's$ 形式的輸入（其中 $p \in B^*$）產生非平凡輸出，我們得到

$${s \in B^\infty \mid x \preceq U(s)} = \dot{\bigcup}_{p \in B^*} {p'} \times {s \in B^\infty \mid x \preceq U(p's) = T_p(s)}$$

我們得到

$$M(x) = P_u({s \in B^\infty \mid x \preceq U(s)})$$
$$= P_u(\dot{\bigcup}{p \in B^*} {p'} \times {s \in B^\infty \mid x \preceq U(p's) = T_p(s)})$$
$$= \sum{p \in B^} P_u(p') \cdot P_u({s \in B^\infty \mid x \preceq T_p(s)})$$
$$= \sum_{p \in B^} 2^{-l(p')} \cdot \nu_p(x)$$
$$= \sum_{\nu \in \mathcal{M}{sol}} \left( \sum{p \in B^*: \nu_p = \nu} 2^{-l(p')} \right) \cdot \nu(x)$$
$$= \sum_{\nu \in \mathcal{M}{sol}} P{ap}(\nu) \cdot \nu(x)$$

證明完畢。 □

這意味著，如果我們的歷史 $x$ 是從 $M$ 採樣的，我們也可以將其視為先以概率 $P_{ap}(\nu)$ 採樣一個 LSCSM $\nu$，然後從 $\nu$ 連續採樣歷史。

如果一個 LSCSM $\nu$ 有一個編碼 $\nu = \nu_p$，那麼 $P_{ap}(\nu) \ge 2^{-l(p')}$。這給出了一種簡單性偏誤：具有簡單（即短）描述 $p$ 的宇宙在這種先驗之先驗下更有可能。這可以被解釋為奧卡姆剃刀的一種形式，即具有短描述的假設獲得指數級更高的權重。^([7])

所羅門諾夫歸納法

到目前為止，我從「我們的宇宙是採樣均勻隨機程序的結果」這一假設出發，得出的結論是：這等同於先以偏好簡單假設的先驗採樣一個 LSCSM，然後從中採樣我們的歷史。因此，在我們的假設下，我們應該預期世界比懷疑論悖論所暗示的更具可預測性：我們可以將推理集中在簡單的宇宙上，並且應該有機會做出優於隨機猜測的預測。我們將在本節中詳細闡述這一點的數學細節。

通用序列預測

鑑於這些想法，我們應該如何進行預測？答案是：我們使用所羅門諾夫混合分佈 $M(x) = \sum_{\nu \in \mathcal{M}{sol}} P{ap}(\nu) \nu(x)$ 本身來進行預測，在觀察到初始歷史 $x_{<t} = x_1, \dots, x_{t-1} \in B^{t-1}$ 後，通過熟悉的條件概率 $M(x_t \mid x_{<t}) := M(x_{\le t}) / M(x_{<t})$ 來預測序列延續。這是進行預測最簡約的方式，假設我們在先驗上僅做出「源自均勻隨機採樣程序」的假設。

我們現在通過將條件概率與貝氏更新聯繫起來，更詳細地解釋如何使用 $M$ 進行預測。對於任何 LSCSM $\nu$，定義條件概率 $\nu(x \mid y) := \nu(yx) / \nu(y)$。我們得到：

$$M(x_t \mid x_{<t}) = \frac{M(x_{\le t})}{M(x_{<t})} = \frac{\sum_{\nu \in \mathcal{M}{sol}} P{ap}(\nu) \nu(x_{\le t})}{\sum_{\nu' \in \mathcal{M}{sol}} P{ap}(\nu') \nu'(x_{<t})}$$
$$= \sum_{\nu \in \mathcal{M}{sol}} \frac{P{ap}(\nu) \nu(x_{<t})}{\sum_{\nu' \in \mathcal{M}{sol}} P{ap}(\nu') \nu'(x_{<t})} \cdot \nu(x_t \mid x_{<t})$$
$$=: \sum_{\nu \in \mathcal{M}{sol}} P{ap}(\nu \mid x_{<t}) \cdot \nu(x_t \mid x_{<t})$$

其中我以建議的方式定義了 $P_{ap}(\nu \mid x_{<t})$。這實際上是傳統意義上的貝氏後驗；通過將 $\nu(x_{<t})$ 寫作 $P(x_{<t} \mid \nu)$（即在假設 $\nu$ 的條件下歷史 $x_{<t}$ 的似然值），可以更清楚地看到這一點。內部公式變為：

$$P_{ap}(\nu \mid x_{<t}) = \frac{P_{ap}(\nu) \cdot P(x_{<t} \mid \nu)}{\sum_{\nu'} P_{ap}(\nu') \cdot P(x_{<t} \mid \nu')} = \frac{P_{ap}(\nu) \cdot P(x_{<t} \mid \nu)}{P(x_{<t})}$$

這就是經典的貝氏定理。

因此，我們得到了一個非常令人滿意的所羅門諾夫歸納法描述：

• 觀察宇宙的歷史 $x_{<t}$。
• 使用先驗之先驗 $P_{ap}(\nu)$ 和每個宇宙規則假設 $\nu$ 的似然值 $\nu(x_{<t})$，通過貝氏推理確定後驗 $P_{ap}(\nu \mid x_{<t})$。
• 使用各個假設的預測 $\nu(x_t \mid x_{<t})$ 的加權平均來預測下一個數據點，權重為它們的後驗概率。

這非常有吸引力：

• 它內建了奧卡姆剃刀，即「假設越簡單越可取」的常見啟發式方法。通常這意味著具有短描述，但在這裡，簡單性的概念被擴展為「通過通用單調圖靈機輸入隨機噪聲而偶然碰到的難易程度」。具有短描述的假設在這種意義上是很有可能的，但這不是唯一的可能性：另一種方式是擁有指數級多的自由選擇，這些選擇導致相同的分佈，就像我們宇宙中坐標系的選擇一樣（參見 Nate 的貼文）。
• 它與使用觀察結果來捨棄或驗證理論的典型科學智慧（貝氏定理）非常兼容。
• 它是數學上精確的。

一個經常被指出的缺點是它是不可計算的，因為我們無法精確確定後驗 $P_{ap}(\nu \mid x_{<t})$ 或條件概率 $\nu(x_t \mid x_{<t})$。然而：

• 我們通常對假設的先驗概率 $P_{ap}(\nu)$ 有很好的直覺。
• 後驗和條件概率中的成分 $\nu(x_{<t})$ 雖然無法計算，但原則上可以從下方逼近，因為 $\nu$ 被假設為下半可計算的。唯一的問題是，在任何有限階段，都不一定能知道逼近的效果有多好。

所羅門諾夫界限

如果這不能導致世界實際的可預測性，那麼這一切都沒有用。畢竟，我們的問題是為什麼我們實際的宇宙是可預測的。幸運的是，事實證明，只要我們的宇宙是由一個下半可計算的測度（而非僅僅是半測度）生成的，所羅門諾夫歸納法就是一個極其出色的預測器。^([8])

定理 5（所羅門諾夫界限）。令 $\mu$ 為無限序列上的任何下半可計算測度，並假設它生成了我們實際的宇宙。定義使用 $M$ 預測由 $\mu$ 採樣的序列的累積預期預測誤差為：

$$S_\mu^\infty := \sum_{t=1}^\infty \sum_{x_{<t} \in B^*} \mu(x_{<t}) \sum_{x_t \in B} (M(x_t \mid x_{<t}) - \mu(x_t \mid x_{<t}))^2$$

那麼我們有

$$S_\mu^\infty \le -\ln P_{ap}(\mu)$$

換句話說，預測誤差的上界是我們真實宇宙的狄拉克測度與我們的先驗之先驗概率 $P_{ap}(\mu)$ 之間的交叉熵損失。特別是，對於越來越長的歷史，總剩餘預測誤差趨於零。^([9])

證明。 我們有（計算後附解釋）：

$$S_\mu^\infty = \sum_{t=1}^\infty \sum_{x_{<t} \in B^} \mu(x_{<t}) \sum_{x_t \in B} (M(x_t \mid x_{<t}) - \mu(x_t \mid x_{<t}))^2$$
$$\le \sum_{t=1}^\infty \sum_{x_{<t} \in B^} \mu(x_{<t}) \sum_{x_t \in B} \mu(x_t \mid x_{<t}) \ln \frac{\mu(x_t \mid x_{<t})}{M(x_t \mid x_{<t})}$$
$$= \lim_{n \to \infty} \sum_{t=1}^n \sum_{x_{<t}} \mu(x_{<t}) D_{KL}(\mu(X_t \mid x_{<t}) \parallel M(X_t \mid x_{<t}))$$
$$= \lim_{n \to \infty} \sum_{t=1}^n D_{KL}(\mu(X_t \mid X_{<t}) \parallel M(X_t \mid X_{<t}))$$
$$= \lim_{n \to \infty} D_{KL}(\mu(X_1, \dots, X_n) \parallel M(X_1, \dots, X_n))$$
$$= \lim_{n \to \infty} \sum_{x_{\le n}} \mu(x_{\le n}) \ln \frac{\mu(x_{\le n})}{M(x_{\le n})}$$

第 1 步是定義。第 2 步是一個標準不等式，只要 $\mu$ 是一個測度即可成立，參見 Hutter 等人的推論 2.8.8^([10])（而 $M$ 允許僅為半測度）。第 3 步使用 KL 散度的定義，並將無限級數改為部分和的極限。第 4 步代入條件 KL 散度的定義。

第 5 步是關鍵的一步。類似於香農熵 $H$ 滿足眾所周知的鏈式法則 $H(X) + H(Y|X) = H(X,Y)$，KL 散度也滿足鏈式法則 $D_{KL}(P(X) \parallel Q(X)) + D_{KL}(P(Y|X) \parallel Q(Y|X)) = D_{KL}(P(X,Y) \parallel Q(X,Y))$。直覺上，在變量 $X$ 中測得的 $P$ 和 $Q$ 的散度，加上在已知 $X$ 的情況下 $Y$ 中的散度，等於 $(X,Y)$ 上的總散度。將此鏈式法則從 1 疊加到 $n$，正好得到第 5 步的結果。該疊加性質的完整證明可在 Hutter 等人的引理 3.2.4 中找到。^([10]) 第 6 步再次僅是 KL 散度的定義。

現在，請注意根據定理 4，我們有

$$M(x_{\le n}) = \sum_{\nu \in \mathcal{M}{sol}} P{ap}(\nu) \nu(x_{\le n}) \ge P_{ap}(\mu) \mu(x_{\le n})$$

利用這個不等式，我們得到

$$S_\mu^\infty \le \lim_{n \to \infty} \sum_{x_{\le n}} \mu(x_{\le n}) \ln \frac{1}{P_{ap}(\mu)} = -\ln P_{ap}(\mu) \cdot \lim_{n \to \infty} \sum_{x_{\le n}} \mu(x_{\le n}) = -\ln P_{ap}(\mu)$$

證明完畢。 □

因此，結合我們之前的調查，我們不僅有理由相信我們的宇宙是可預測的，而且還存在一個驚人的預測器，只要我們的宇宙是由下半可計算測度生成的；這解決了引言中的懷疑論悖論。此外，這個預測器是由一個不假設任何關於我們宇宙先驗知識的空白狀態概率分佈 $M$ 給出的。雖然對於在 $P_{ap}$ 下更有可能的宇宙（包括具有短描述的宇宙），預測誤差更低，但我注意到，無論 $\mu$ 是什麼，對於長歷史，預測誤差都會趨於零。

與基於 K 複雜度的所羅門諾夫歸納法之比較

本節將我們的所羅門諾夫歸納法構造與更常見的構造進行比較，後者將先驗 $P_{ap}$ 替換為所羅門諾夫先驗 $P_{sol}$。如果你對此不感興趣，請直接閱讀結論。本節假設讀者具備比前幾節更多的背景知識。

假設我們有一個 LSCSM 的可計算枚舉 $\nu_1, \nu_2, \dots$。例如，我們可以通過將自然數 $i$ 映射到其二進位表示（即代碼 $p$），然後定義 $\nu_i := \nu_p$ 來實現。此外，令 $U_{pr}$ 為一個單獨的通用前綴圖靈機，它與通用單調圖靈機 $U$ 沒有直接關係。定義自然數 $i$ 的柯氏複雜度 $K(i)$ 為輸入到 $U_{pr}$ 並計算出 $i$ 的二進位編碼的最短輸入長度。那麼所羅門諾夫先驗由下式給出：

$$P_{sol}(i) := 2^{-K(i)}$$

然後可以證明，在大約（即最多差一個常數倍數）的意義下，我們有

$$M(x) \approx \sum_{i \in \mathbb{N}} P_{sol}(i) \nu_i(x)$$

參見 Li 和 Vitányi ^([1]) 定理 4.5.3。我將在第二小節的開頭證明這一陳述，以揭示 $P_{ap}$ 的一個優勢。^([11]) 重要的是，由於定理 4，這意味著所羅門諾夫先驗 $P_{sol}$ 和先驗之先驗 $P_{ap}$ 在序列預測上導致的結果在常數倍數內是相同的。因此，我們分析的先驗優勢並非關於它們誘導的預測分佈。

Psol 相對於 Pap 的優勢

所羅門諾夫先驗具有一些我們定義中所缺失的獨特優勢：

下半可計算性： 權重 $2^{-K(i)}$ 是下半可計算的，而我們的權重 $P_{ap}(\nu)$ 可能不是。原因是為了逼近 $P_{ap}(\nu)$，我們需要能夠通過算法確定對於任何二進位字串 $p$，是否 $\nu_p = \nu$。目前似乎沒有方法能做到這一點。有關在 Nate 的替代複雜度相關案例中缺失下半可計算性的更多細節，請參見我們的腳註調查。^([12])

在 UTM 變更下的不變性： 權重 $2^{-K(i)}$ 在 $U_{pr}$ 變更時，在常數倍數內是不變的。相比之下，$P_{ap}(\nu)$ 在通用單調機器 $U$ 變更時不具備不變性，甚至在常數倍數內也不具備。我從 Cole Wyeth 那裡學到了以下論據。即，取你的通用單調圖靈機 $U$。從中定義第二台機器 $W$，其給定為 $W((pp)'q) := U(p'q) = T_p(q)$，對任何其他輸入輸出為空。我們可以很容易地看到這也是一台通用單調圖靈機。利用暗示性的符號，我們得到：

$$P_{ap}^W(\nu) = \sum_{r \in B^: \nu_r^W = \nu} 2^{-l(r')} = \sum_{p \in B^: \nu_p = \nu} 2^{-l((pp)')} \lesssim \left( \sum_{p \in B^*: \nu_p = \nu} 2^{-l(p')} \right)^2 = P_{ap}(\nu)^2$$

因此，如果 $P_{ap}(\nu)$ 非常小，那麼 $P_{ap}^W(\nu)$ 就會變得極小，不存在常數因子 $c$ 使得 $P_{ap}^W(\nu) \ge c \cdot P_{ap}(\nu)$。我們注意到，在近似不等式中，我們使用了 $l((pp)') \approx 2l(p')$，這僅在對數誤差項內成立，但可能不會實質性地改變結論。

此外，這也意味著先驗之先驗 $P_{ap}$ 與基於 K 複雜度的所羅門諾夫先驗 $P_{sol}$ 之間沒有簡單的關係可以獨立於所涉及的通用圖靈機的選擇而成立。鑑於編碼定理表明字串的先驗概率在常數倍數內與其 K 複雜度相同，這可能會令人驚訝。這一觀察與我的信念有關，即 Nate 的貼文中的替代複雜度和 K 複雜度在常數倍數內並非相同，這與幾位評論者的說法相反。我在腳註中對此進行了更詳細的討論。^([12])

所羅門諾夫先驗的最優性： 假設我們留在下半可計算半概率質量函數 $\omega(i)$ 的領域（$P_{sol}(i)$ 是其中一個例子），並考慮混合 $\sum_i \omega(i) \nu_i$。在所有這些對 $\omega$ 的選擇中，所羅門諾夫先驗 $P_{sol}(i) = 2^{-K(i)}$ 在某種意義上是最優的。即，令 $P_1, P_2, \dots$ 是所有下半可計算半概率質量函數的枚舉。那麼對於所考慮的每個 $\omega$，都存在一個 $j^$ 使得 $\omega = P_{j^}$。根據編碼定理（Li 和 Vitányi 定理 4.3.3 ^([1])），我們有

$$2^{-K(i)} \approx \sum_{j \ge 1} 2^{-K(j)} P_j(i) \ge 2^{-K(j^)} P_{j^}(i) \approx \omega(i)$$

在最後一步中差一個常數倍數 $2^{-K(j^*)}$。換句話說，$P_{sol}$ 在所有索引 $i$ 上的「權重」都比 $\omega$ 大。因此，當將定理 5 改編為通用的下半可計算混合而非 $M$ 時，$P_{sol}$ 提供了比 $\omega$ 更好的界限（在加性常數範圍內）：

$$-\log P_{sol}(i) = K(i) \le -\log \omega(i)$$

對於我們的先驗之先驗 $P_{ap}(\nu)$，似乎不存在任何類似的結果。事實上，如果存在這樣的結果反而會令人驚訝，因為這種先驗在通用單調圖靈機變更時是非常不具不變性的。另一方面，$P_{ap}$ 可能不是下半可計算的，這一事實意味著 $P_{sol}$ 不一定能勝過 $P_{ap}$。

Pap 相對於 Psol 的優勢

依賴的選擇更少： $P_{sol}$ 的定義取決於通用前綴機器 $U_{pr}$ 的選擇，此外還取決於我們之前已經使用的 $U$ 的選擇。$P_{ap}$ 則沒有這種進一步的依賴。

Pap 是柏拉圖式的，Psol 則不是： 定理 4 非常自然：證明基本上是從 $P_{ap}$ 的定義本身揭示出來的，由於這個美麗的結果，該定義獲得了內在的正當性。相比之下，關於

$$M(x) \approx \sum_{i=1}^\infty 2^{-K(i)} \nu_i(x) =: \xi_{U_{pr}}(x)$$

的類似陳述僅非常鬆散地依賴於 $M$ 和所羅門諾夫先驗 $P_{sol}(i) = 2^{-K(i)}$ 的定義，這意味著我們可以選擇一個非常不同的先驗而不會產生太多負面後果。為了說明這一點，我陳述該結果的證明：$M$ 本身是一個 LSCSM，這意味著 $M = \nu_{i_0}$（對於某個 $i_0 \in \mathbb{N}$）。這導致

$$\xi_{U_{pr}}(x) \ge 2^{-K(i_0)} \nu_{i_0}(x) = c \cdot M(x)$$

這已經在一個方向上建立了不等式（在常數倍數內）。對於另一個方向，首先注意 $\xi_{U_{pr}}$ 是下半可計算的，因為 $2^{-K(i)}$ 和每個 $\nu_i$ 都是下半可計算的。此外，我們有

$$\xi_{U_{pr}}(x) = \sum_{i=1}^\infty 2^{-K(i)} \nu_i(x) \ge \sum_{i=1}^\infty 2^{-K(i)} (\nu_i(x0) + \nu_i(x1)) = \xi_{U_{pr}}(x0) + \xi_{U_{pr}}(x1)$$

這幾乎將 $\xi_{U_{pr}}$ 確立為一個 LSCSM，除了它不滿足我們 $\xi_{U_{pr}}(\epsilon) = 1$ 的假設。因此，定義 $\tilde{\xi}{U{pr}}$ 與 $\xi_{U_{pr}}$ 相同，除了 $\tilde{\xi}{U{pr}}(\epsilon) = 1$。那麼這就是一個 LSCSM，我們得到

$$M(x) = \sum_{\nu \in \mathcal{M}{sol}} P{ap}(\nu) \nu(x) \ge P_{ap}(\tilde{\xi}{U{pr}}) \tilde{\xi}{U{pr}}(x) \ge P_{ap}(\tilde{\xi}{U{pr}}) \xi_{U_{pr}}(x)$$

這正是另一個方向上所需的不等式。正如我們所見，這個定理僅取決於 $M$ 和 $\xi_{U_{pr}}$（本質上）都是所有 LSCSM 的混合這一事實；$M$ 和 $\xi_{U_{pr}}$ 的具體細節並不重要，對於任何其他所有 LSCSM 的下半可計算混合，同樣的比較也成立。因此在我看來，所羅門諾夫先驗 $P_{sol}(i) = 2^{-K(i)}$ 最終是任意的，缺乏先驗的正當性。

Pap 導致更少的常數： 與前幾點相關，$M(x)$ 作為 $\sum_i 2^{-K(i)} \nu_i(x)$ 的表示僅在常數倍數內成立，而定理 4 是一個精確的等式。Hutter 等人的定理 3.8.8 ^([10]) 聲稱，通過巧妙選擇兩台通用圖靈機 $U$ 和 $U_{pr}$，可以實現精確等式，但我不確定這種選擇是否能以一種令人滿意的方式在「先驗」上得到證明。

結論

在本文中，我介紹了不使用 K 複雜度的所羅門諾夫歸納法：當採樣均勻隨機程序代碼並將其輸入通用單調圖靈機時，關於我們宇宙的假設（模型化為下半可計算半測度 LSCSM）被認為與其「真實存在」的可能性一樣大。幾乎是套用定義地，這意味著使用通用機器採樣歷史 $x$ 的概率，等於在先從先驗之先驗中採樣一個 LSCSM 後，再從該 LSCSM 採樣歷史的概率（定理 4）。

接著，我將所羅門諾夫歸納法定義為：在假設序列是由均勻隨機電腦程序生成的基礎上，預測序列延續的過程。應用定理 4 則引出了關於先驗之先驗的等效描述：要延續一個序列，首先通過貝氏推理形成假設的後驗分佈，然後使用後驗分佈的混合來預測延續。由於假設的先驗分佈具有簡單性偏誤（具有較短編碼的假設更有可能），這可以被視為奧卡姆剃刀的形式化。

在定理 5 中，我們看到了著名的所羅門諾夫界限。它表明，在任何被計算的宇宙中預測延續的累積誤差，其上界是該宇宙在先驗之先驗下的概率的負對數，即交叉熵損失。這解決了引言中的歷史困惑，並解釋了預測是如何可能的，僅使用了「我們的宇宙是被計算出來的」這一合理假設。

隨後，我將先驗之先驗與基於 K 複雜度的所羅門諾夫先驗進行了比較，發現後者具有一些獨特的數學優勢：該先驗是下半可計算的、在通用前綴圖靈機變更下具有不變性，並且在與其他下半可計算先驗比較時，它能導致最優的所羅門諾夫界限（然而，這不一定優於定理 5 中的界限，因為先驗之先驗可能不是下半可計算的）。這意味著所羅門諾夫先驗可能是進一步發展理論的更好數學基礎。

然而，先驗之先驗似乎最終更自然，因為它不依賴於通用前綴機器的額外選擇，且通用分佈的混合描述（定理 4）是套用定義即成立的——而不是像所羅門諾夫先驗那樣，通過涉及進一步常數倍數誤差的事後分析來實現。正如 Cole Wyeth 向我提到的，或許可以通過類似於 Friedberg 編號 的構造，為每個 LSCSM 找到一個唯一的編碼，從而統一這兩個視角。這或許能在這種設定下挽救編碼定理（即退化與簡單性，或替代複雜度與 K 複雜度之間的對應關係）。

FAQ（常見預期問題）

在這裡，我回答一些我經常預見到的問題。

問： 在我們的宇宙中，我們觀察到的並非直到目前為止的完整歷史 $x_1, \dots, x_t$。相反，我們是在有限的時間內觀察宇宙的一小部分。現實中的序列預測如何與所羅門諾夫歸納法兼容？

答： 現實中的假設 $\nu$ 不僅是宇宙的模擬器，更是你在宇宙中精確觀察結果的模擬器。因此，$\nu$ 包含了對宇宙的描述以及對你在時空中位置的描述。另一個複雜之處在於我們的感知是「感質」（qualia），我們不知道如何將其與符號字串的形式化聯繫起來，參見 Wei Dai 關於開放問題的貼文。

問： 我們應該嘗試使用所羅門諾夫歸納法來預測現實世界嗎？

答： 那是相當難以處理的，所以我們必須使用替代方案。問題在於它是否是一個有用的逼近目標。我的猜測是這取決於時間尺度：我們觀察的歷史越短，我們就越應該信任由進化刻在我們腦海中的先驗，因為它們可能比所羅門諾夫先驗更好，且更適應我們實際的宇宙。在長期的時間跨度上，逼近所羅門諾夫歸納法或許會變得越來越有用。

問： 神經網絡在任何有意義的意義上執行所羅門諾夫歸納法嗎？

答： 神經網絡與所羅門諾夫歸納法之間有一個有趣的類比：正如我們版本的所羅門諾夫歸納法通過將隨機噪聲輸入通用圖靈機來預測序列延續，神經網絡函數在初始化時也是通過在架構中排列隨機參數來採樣的。如果梯度下降此外還類似於貝氏更新，那麼這種類比可能會變得非常接近。如果在所羅門諾夫語境下，概率與 K 複雜度之間存在足夠強的聯繫（如特定情況下的編碼定理），那麼人們可能會推論神經網絡也具有向具有短描述的學習函數傾斜的偏誤，這或許解釋了它們的泛化能力。另見此處、此處和此處。

問： 所羅門諾夫先驗分佈 $M$ 只是一個有用的模型，還是你真的預期我們的世界是從中採樣的？它是萬有理論嗎？

答： 我的直覺是它只是一個有用的模型。它取決於通用單調圖靈機 $U$，這感覺很不自然。我也不確定我們的宇宙是否真的是離散且被計算出來的。或許我們生活在一個連續的數學結構中，時間只是在我們的經驗中產生？我還沒有深入研究數學結構與圖靈機之間的精確重疊和對應關係，歡迎有人在評論中發表更多見解。

問： 字串在通用單調圖靈機下的複雜度，與在其他圖靈機模型（可能更接近我們通常編寫代碼的編程語言）下的複雜度有何關係？

答： 有幾個界限將不同的編碼長度緊密聯繫在一起，通常最多差一個對數誤差項。例如，參見 Hutter 等人的定理 3.8.7。^([10])

---

• ^(^) M. Li and P. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications. Springer Cham, 4th edition, 2019. ISBN 9783030112974., DOI: 10.1007/978-3-030-11298-1.
• ^(^) 我發現文獻中關於單調圖靈機是僅對部分輸入有輸出的「部分函數」還是「全函數」存在歧義。我選擇了全函數，因為這使概念更簡單，且似乎是最常見的觀點。
• ^(^) 正式地，可以將此極限定義為前綴關係上的上確界（supremum）。
• ^(^) 在文獻中，通常會遇到 $\nu(\epsilon) \le 1$ 的定義；然而，對於我們的目的，等號更自然，且稍後將確保所有下半可計算半測度都能由單調圖靈機表示。
• ^(^) 令人困惑的是，Li 和 Vitányi 使用了 $\nu(\epsilon) \le 1$ 的 LSCSM 定義（與我們 $\nu(\epsilon) = 1$ 的定義不同），卻聲稱它們都被單調圖靈機覆蓋。或許他們使用了某種不同的單調圖靈機 $T$ 定義，其中允許輸出完全「未定義」（因此甚至不是空字串），這意味著 $\nu_T(\epsilon) < 1$，而我們的單調圖靈機是全函數。這篇論文認為 Li 和 Vitányi 犯了一個錯誤，並寫道：「這等同於 [LV08] 中的定理 4.5.2（第 301 頁），但有一個小修正：根據構造，任何 $T$ 都有 $\lambda_T(\epsilon) = 1$，但 $\mu(\epsilon)$ 可能不為 1，因此必須排除這種情況。」
• ^(^) $P_{ap}$ 實際上是一個嚴格的概率質量函數，這意味著 $\sum_\nu P_{ap}(\nu) = 1$。原因是每個 $s \in B^\infty$ 都可以表示為 $s = p't$（其中 $p \in B^$ 且 $t \in B^\infty$），所有具有相同前綴 $p'$ 的 $s$ 加在一起的權重為 $2^{-l(p')}$。因此，$1 = P(B^\infty) = \sum_{p \in B^} 2^{-l(p')} = \sum_\nu P_{ap}(\nu)$。
• ^(^) 反之則不一定成立：一個假設可能僅僅因為擁有指數級多的（較長）描述而獲得很大權重，而先驗上並不能保證一定存在一個短描述。為了獲得關於這一視角的直覺，我推薦 Nate 關於替代複雜度的貼文和最後一個腳註。^([12])
• ^(^) 換句話說，該定理假設我們的宇宙不能在任何有限時間內簡單地結束，而「半測度」則總是可以停止序列延續。這起初看起來很嚴格，並且會排除像大擠壓（big crunch）（宇宙最終結束）這樣的可能性。然而，我認為即使在真正的測度形式體系中，這種情況也可能得到挽救：對於一個結束的序列，只需用 $000\dots$ 將其延續為無限序列。通過這種方法，應該可以為任何半測度分配一個測度，希望它具有類似的先驗概率。如果是這樣，我們仍然能夠有效地預測我們實際的宇宙，直到它結束的那一刻，而那時正確預測已經不再重要了。我沒有詳細檢查這些說法，但或許這篇貼文中的引理 1 已經包含了答案。
• ^(^) 請注意，我們也可以將此誤差寫為期望值 $S_\mu^\infty = E_{s \sim \mu} [\sum_{t=1}^\infty \sum_{x_t \in B} (M(x_t \mid s_{<t}) - \mu(x_t \mid s_{<t}))^2]$，這在概念上更清楚地表明它是一個累積預期預測誤差。
• ^(^) Marcus Hutter and David Quarel and Elliot Catt. An Introduction to Universal Artificial Intelligence. Chapman & Hall, 2024. ISBN: 9781032607023, DOI: 10.1201/9781003460299.
• ^(^) 讀者可能會好奇為什麼我們要費力使用一個單獨的通用前綴機器。令 $p = bin(i)$，另一個選擇是定義 $P(i) := 2^{-l(p')}$ 作為 $\nu_i = \nu_p$ 的權重。這個定義的問題在於（或許有些矛盾），$P$ 此時是可計算的，根據 Li 和 Vitányi 的引理 4.3.1 ^([1])，這導致 $P$ 不是通用的，即它不能支配所有其他可計算（更不用說下半可計算）的半測度。這反過來意味著該先驗不會導致我們將要解釋的 $P_{sol}(i) = 2^{-K(i)}$ 所具有的最優界限。
• ^(^) Nate 假設存在一種通用編程語言 $U$，它可以接收輸入代碼 $p$，然後通過 $U$ 產生輸出函數 $f$。$p$ 的例子是「快速排序」或「冒泡排序」的代碼，它們都指向同一個函數 $f$（接收列表並輸出排序後的版本）。他隨後定義了 K 複雜度 $K_U(f) := \min {l(p) \mid eval_U(p) = f}$，以及替代複雜度 $K_U^{alt}(f) := -\log_2 \sum_{p: eval_U(p)=f} 2^{-l(p)} =: -\log_2 P_U(f)$。許多評論者聲稱這兩者僅差一個加性常數，但我認為這是錯誤的。

乍看之下這似乎是真的，因為它看起來與編碼定理相同，後者是關於通用前綴機器的 $K(x)$ 與 $-\log_2 P(x)$ 的相等性（$x$ 為二進位字串）。編碼定理的證明關鍵在於 $P(x)$ 的下半可計算性，這是通過交替執行（dovetailing）所有 $p$ 並檢查通用前綴機器是否將它們發送到 $x$ 來實現的，當發生這種情況時，將 $P(x)$ 的估計值增加 $2^{-l(p)}$。這些估計值對於找到長度逐漸變短並最終逼近 $-\log_2 P(x)$ 的 $x$ 的碼字至關重要，從而建立了與 $K(x)$ 的近似相等。

同樣的證明策略不適用於 Nate 的替代複雜度 $K_U^{alt}$，因為據我所知，不可能存在一個算法能檢查任何程序 $p$ 和函數 $f$ 是否滿足 $eval_U(p) = f$；畢竟，等式兩邊本身都是函數，原則上可以接收無限多個輸入，我們無法遍歷所有輸入（參見 萊斯定理 Rice's theorem）。因此，$P_U$ 的下半可計算性似乎失效了，因此我不知道有什麼方法可以構造出最終能逼近長度 $-\log_2 P_U(f)$ 的碼字。因此，在這種語境下，編碼定理很可能失效，除非存在完全不同的成功證明策略。