程序員用1個概率數，把圖靈機逼進了死胡同

1966年，19歲的Gregory Chaitin在IBM做暑期工時，順手寫了個證明。沒人想到，這個證明里的一個數，會讓半個多世紀后的程序員在深夜盯著屏幕發呆——它定義了"隨機程序停機的概率"，卻連它小數點后第一位都算不出來。

這就是Ω（歐米茄），計算機科學里最囂張的常數。它不是π那種"算不完但你能算"的數，而是"算不了"——沒有任何算法能算出它的任何一位，連猜都猜不準。

Chaitin后來回憶，這個靈感來自哥德爾不完備定理和圖靈停機問題的"雜交"。圖靈證明了不存在通用算法能判斷任意程序是否停機；Chaitin則問：如果隨機生成一個程序，它停機的概率是多少？這個概率值本身，就成了不可計算的化身。

前綴自由：給程序語言加條奇怪的規矩

要理解Ω，得先接受一個反直覺的設定：程序語言不能允許"一個程序是另一個程序的前綴"。

什么意思？正常編程里，"print"和"printline"可以共存，后者是前者的擴展。但在Chaitin的構造里，這是非法的。如果"01"是個有效程序，那"011"、"010"、"0110"統統不能是程序——系統必須能"即時"判斷程序何時結束，不需要結束符。

這種編碼叫前綴自由碼（prefix-free code），1948年香農在信息論里用過。Chaitin把它焊死在計算理論里：通用計算機F讀取輸入時，一個比特一個比特地讀，自己決定何時停手，剩下的比特全作廢。

這設計像什么？像自助餐廳里"拿多少算多少，不能回盤"的規則。你端走的盤子（程序）一旦確定，后面的人不能在你盤子上加菜（擴展）冒充新盤子。

滿足這個條件的F叫前綴自由通用可計算函數。Chaitin證明：這種F存在，而且任何合理的編程語言都能被改造成這樣。

Ω的構造：把停機問題燉成一鍋概率

現在，假設你用前綴自由語言F隨機寫程序。怎么隨機？拋硬幣：正面寫0，反面寫1，直到F說"停，這串比特夠成一個程序了"。

每個長度n的程序出現概率是2??。把所有會停機的程序概率加起來：

Ω = Σ 2?|p|，其中p遍歷所有使F(p)停機的程序

這個求和收斂，因為前綴自由性保證了程序不會重疊，總概率不超過1。Ω是個0到1之間的實數，二進制展開形如0.1100101...

關鍵來了：知道Ω的前n位，就能解決長度≤n的所有停機問題。

算法很簡單：枚舉所有程序，按長度優先運行，累計它們的貢獻。當累計值逼近Ω的前n位、且下一個程序會讓總和超過Ω時，那個程序就是不停機的。反之，若累計能精確匹配Ω的某前綴，已枚舉的程序就是全部停機程序。

但這里有個死循環——你得先知道Ω的前n位，才能算這個。而Ω本身又依賴于停機問題的解。

不可計算性的三重封印

Chaitin給Ω上了三道鎖。

第一，不可計算：沒有算法能算出Ω的任意一位。如果能算，就能解決停機問題，與圖靈1936年的結論矛盾。

第二，Martin-L?f隨機：這是算法隨機性的金標準。一個序列是Martin-L?f隨機的，當且僅當不存在任何有效統計檢驗能把它和真隨機序列區分開。Ω的每一位都不可預測——即使你知道前n位，第n+1位是0還是1的概率嚴格等于1/2，沒有任何算法能把這個概率提升到50%以上。

第三，超越數且正規：Ω是超越數（不是任何整系數多項式的根），且在任何進制下，每個數字出現的頻率趨于均勻。這些性質本身不稀奇，但和前兩重封印疊加，就成了"最隨機的數學對象"。

Chaitin在1975年的論文里寫：「Ω是算術的磐石，數學的珠穆朗瑪峰。」這話現在看仍不夸張——它把"隨機性"從概率論拖進了計算理論，證明隨機性可以有嚴格的數學定義，且這個定義和不可計算性等價。

不同編碼，不同的Ω

嚴格來說，Ω不是"一個"數，而是一族數。每個前綴自由通用可計算函數F對應一個Ω_F。換編程語言，Ω就變。

但所有Ω共享核心性質：都不可計算，都Martin-L?f隨機，都編碼了停機問題的全部信息。Chaitin把具體編碼稱為"Chaitin構造"，用Ω泛指這一族數——就像程序員說"那個bug"時，大家都知道指什么，盡管每個項目的bug具體內容不同。

這種"家族相似性"讓Ω既有具體構造（你能寫代碼近似它），又有抽象統一性（任何合理計算模型都逃不掉）。

2000年后，Ω找到了意外應用。在算法信息論里，它成了"算法熵"的基準：一個對象的Kolmogorov復雜度（最小程序長度）可以用Ω的近似來界定。在機器學習理論中，Ω的隨機性被用來證明某些學習任務的計算下界——有些規律，識別它們比生成它們更難，難到和計算Ω等價。

更前沿的方向是"具體Ω"：用特定編程語言（如Lisp的某種變體）實際構造Ω的前幾位。Cristian Calude等人2002年算出了某種Lisp方言的Ω前64位。這工作像用望遠鏡拍黑洞——你知道那個數存在，知道它的大部分性質，卻只能瞥見最邊緣的像素。

Chaitin本人晚年轉向元生物學，用Ω類比DNA的進化信息。這個類比有爭議，但核心直覺動人：生物進化也是"隨機程序搜索"，而Ω刻畫了這種搜索的極限效率。

2024年，一位Reddit用戶在r/compsci發帖：「我花了三周試圖用神經網絡預測Ω的位模式，最后才理解為什么這是不可能的。」帖子獲得2300贊，置頂回復是：「歡迎加入'先以為能算，再發現不能算'俱樂部，會員包括1936年以來的所有聰明鬼。」

這個回復的點贊數還在漲。而Ω的第65位，和1948年一樣，仍然藏在硬幣的反面里——你永遠拋不到的那一面。