導(dǎo)語

Kolmogorov使用了三條公理奠定了當(dāng)今概率論的基礎(chǔ)。然而據(jù)傳，他本人對此并不滿意。本文將從可計算性理論的角度向您介紹超越Kolmogorov公理的對于概率論的鮮為人知的全新理解。

關(guān)鍵詞：概率論、隨機(jī)性、圖靈停機(jī)、Martin-L?f隨機(jī)性、可計算性

羅浩源（賓夕法尼亞州立大學(xué)在讀博士）丨作者

萬能的上帝可以解出哥德巴赫猜想嗎

上帝是萬能的嗎？大概不是吧。哲學(xué)家給出了這樣的論述。如果上帝是萬能的，那他應(yīng)該能創(chuàng)造一個自己也舉不起來的石頭。但如果他自己也舉不起來這塊石頭，他還是萬能的嗎？或許您會覺得哲學(xué)家的這個詭辯荒誕不經(jīng)，但如果我換一個問法，您會立馬意識到其中的價值。

我們寫程序時都非常討厭程序陷入死循環(huán)，那么是否存在這樣一個全知全能的程序 ，我們輸入一個程序源代碼的字符串 ，以及打算喂給該程序的輸入字符串，它可以自動判斷源碼所描述的程序在輸入字符串上是否會陷入死循環(huán)。如果假設(shè)這樣的程序存在，通過類似于上面關(guān)于萬能上帝的討論，我們可以很容易地推出矛盾，從而證偽這個命題。

圖靈停機(jī)問題的推理過程：

1. 假設(shè)存在這樣一個全知全能的程序 H，它能判斷任意一個程序 P 和輸入 I，P 在輸入 I 時是否會停機(jī)（不會死循環(huán)）。

   1. if H(P,I) == "會停機(jī)":

      return "是" # 不會死循環(huán)

      else:

      return "否" # 死循環(huán)

2. 構(gòu)造一個新程序 D，它的行為如下：

• D 接受一個程序 Q 作為輸入。

• D(Q) 的邏輯：

• 用 H(Q, Q) 判斷 Q 在輸入 Q 時是否會停機(jī)。

• 如果 H(Q, Q) 說“會停機(jī)”，則讓 D(Q) 進(jìn)入死循環(huán)。

• 如果 H(Q, Q) 說“不會停機(jī)”，則讓 D(Q) 立刻停機(jī)。

def D(Q):

if H(Q, Q) == "會停機(jī)":

while True: # 死循環(huán)

pass

else:

return 0 # 立刻停機(jī)

3. 讓 D 輸入自己 D(D)

• 如果 H(D, D) 說“會停機(jī)”，那么根據(jù) D 的定義，D(D) 會死循環(huán)（矛盾）。

• 如果 H(D, D) 說“不會停機(jī)”，那么根據(jù) D 的定義，D(D) 會立刻停機(jī)（矛盾）。

• 也就是說，無論 H 怎么判斷，都會產(chǎn)生矛盾。

“判斷程序是否陷入死循環(huán)”就是大名鼎鼎的停機(jī)問題，這個全知全能的程序并不存在就是人們常說的停機(jī)問題不可判定。但稍微了解過數(shù)學(xué)史的讀者很快便能意識到，這就是引起第三次數(shù)學(xué)危機(jī)的羅素悖論的變體，而這與哥德爾不完備性定理也有千絲萬縷的聯(lián)系。上面關(guān)于停機(jī)問題的論述并沒有使用任何具體的構(gòu)造，但卻清楚地表明了一個事實，即便計算機(jī)解決了當(dāng)今無數(shù)的難題，創(chuàng)造了無盡的財富，總有一些問題是永遠(yuǎn)沒有辦法使用計算機(jī)解答的，量子計算機(jī)也不行。我們稱這類問題是不可計算的。作者在后文將會指出，我們能夠精確計算的問題其實少得可憐。

事實上，如果這樣一個全知全能的程序真的存在，它可以輕松地回答當(dāng)今困擾無數(shù)數(shù)學(xué)家的難題。例如哥德巴赫猜想：任一大于2的偶數(shù)都可寫成兩個素數(shù)之和。

我們只需要寫一個程序，其中使用while循環(huán)依次枚舉大于2的所有偶數(shù)，在循環(huán)體中依次嘗試所有不大于當(dāng)前偶數(shù)的素數(shù)組合，看看其中是否有一個組合能滿足哥德巴赫猜想的要求。如果某個偶數(shù)不能滿足要求，使用break語句終止while循環(huán)然后輸出0，反之就一直計算下去。

若這樣的全知全能的程序真的存在，我們只需要用它判斷一下上一段中所描述的程序是否會陷入死循環(huán)便可以輕而易舉地知道哥德巴赫猜想是否正確。哥德巴赫猜想至今仍未被完全證明的事實也從側(cè)面印證了這樣的全知全能的程序并不存在，不可計算的問題是很多的。但不可計算并不意味著我們無能為力，在Martin-L?f隨機(jī)性的觀點下，正是從不可計算的局限性中涌現(xiàn)出了概率。

數(shù)學(xué)上一個程序長啥樣

圖靈在1936年提出了計算機(jī)的理論模型——圖靈機(jī)。上圖便是圖靈機(jī)的示意圖。無窮長的紙帶上，每一格可以打點也可以留空，有一個讀取寫入頭在紙帶上移動，并修改紙帶上的數(shù)據(jù)。讀取寫入頭有很多不同的狀態(tài)，以及一系列的指令。例如，在上圖中，(qi, _ , qj , * , ←)指令的含義是，若讀取寫入頭當(dāng)前是“qi”，當(dāng)前讀到了空格“_”，那么將當(dāng)前狀態(tài)改為“qj”，在當(dāng)前空格中寫入“*”，最后向左手移動。而在圖片所表示的例子中，讀取寫入頭的當(dāng)前狀態(tài)是“qk”，讀取到的信息是“*”，于是匹配到第二條指令，將當(dāng)前狀態(tài)改為“qh”，擦除當(dāng)前格子中的“*”，最后向右移動。讀取寫入頭有一個最終狀態(tài)，當(dāng)達(dá)到最終狀態(tài)后它停止工作，此時我們稱圖靈機(jī)停機(jī)，表示計算完成，而紙帶上的信息就是計算的結(jié)果。

圖靈機(jī)刻畫了人類和計算機(jī)的計算過程，是一個相當(dāng)成功的模型。但若想要研究到底什么問題是可計算的，什么是不可計算的，直接構(gòu)造圖靈機(jī)寫出指令還是太麻煩了。回想我們在實際編程中是如何操作的，我們把機(jī)器語言封裝成匯編語言，又把匯編語言封裝成其他高級語言，通過代碼庫的復(fù)用簡化我們的思維過程。于是數(shù)學(xué)家將圖靈機(jī)可以實現(xiàn)的基本操作封裝成了如下的5個api?？紤]滿足如下公理的、輸入是有限位自然數(shù)、輸出是一個自然數(shù)的函數(shù)的最小集合 C。它們滿足：

1. 自增函數(shù)在C中。即C中存在一個函數(shù)s, s(n)=n+1。

2. 所有的常數(shù)函數(shù)在C中。即對于任意的m，都存在一個函數(shù)cm, cm(x1, …, xk)=m，cm在函數(shù)集合C中。

3. 投影函數(shù)在C中。即對于任意的正整數(shù)k和不大于k的正整數(shù)i，到第i位的投影pi(x1, … , xk)=xi 在C中。

4. 函數(shù)的復(fù)合在C中。即，若g1, … gk 和h在C中，那么h(g1, … , gk)也在C中。

5. 遞歸函數(shù)在C中。即，若g和h在C中，g的輸入為k元自然數(shù)數(shù)組，h的輸入為k+2元自然數(shù)數(shù)組，則在C中存在函數(shù)f，滿足f(0, x1, … , xk)=g(x1, … xk), 且f(n+1, x1, … xk)=h(n, x1, … xk, f(n, x1, … xk))。

數(shù)學(xué)家們把這樣最小的函數(shù)集合C叫做原始遞歸函數(shù)（primitive recursive function），也就是使用這五個api可以組合出的所有運算的全體。這五個“基礎(chǔ)api”或者五條公理看似平平無奇，但是千萬不要因此小看了原始遞歸函數(shù)，事實上，通過原始遞歸函數(shù)我們可以表達(dá)出任何不使用while循環(huán)的算法。若您不信，您可以自己動手試試。

通過遞歸函數(shù)，我們可以表達(dá)出加法，有了加法，使用遞歸便有了乘法。通過遞歸，我們還可以定義減法，只不過a-b在b比a大時輸出0。通過遞歸，我們還可以定義一個函數(shù)σ，它在任意非零自然數(shù)上輸出1，而在0上輸出0，于是只需要計算σ(a-b)，便可以比較a和b的大小。從而類似地可以定義布爾運算。而如果f是一個判斷函數(shù)，當(dāng)條件滿足時輸出1，反之輸出0，使用乘法，f*g+(1-f)*h，便是一條if-else語句，當(dāng)f的條件滿足時該表達(dá)式輸出函數(shù)g的計算結(jié)果，反之則輸出h的計算結(jié)果。同時通過遞歸我們還可以定義do循環(huán)。

看到這里您或許會問，原始遞歸函數(shù)確實有很強(qiáng)的表達(dá)能力，但是各種列表操作它能做到嗎？答案是能！通過原始遞歸函數(shù)，我們可以表示出帶余數(shù)的除法，從而可以通過除法進(jìn)行因式分解。我們把列表的各個元素藏在自然數(shù)的因數(shù)中即可。例如2^5*3^8*5^1*7^10，就表示一個(5, 8, 1, 10)的動態(tài)列表。

至此，我們可以肯定，所有不使用while循環(huán)的算法都可以用一個原始遞歸函數(shù)來表示，同時因為沒有使用while循環(huán)，原始遞歸函數(shù)都會在有限步之內(nèi)停止并給出確定的結(jié)果，所以原始遞歸函數(shù)都是可計算的（但并非所有可計算函數(shù)都是原始遞歸函數(shù)，因為某些使用了while循環(huán)的算法也可以給出確定的結(jié)果）。沒有while循環(huán)，我們的api還是不夠強(qiáng)大。那么，while循環(huán)呢？其實我們只需要再封裝一個api或者說在集合 C中再加一條公理：

1. 若一個k+1位輸入的函數(shù)θ在C中，那么在C中有一個函數(shù)ψ(x1, … , xk)，若θ(x1, … xk, i) 在i

于是這樣，我們便刻畫了while循環(huán)。這個新的函數(shù)集合比原始遞歸函數(shù)的集合更大，我們稱它是μ-遞歸函數(shù)（μ-recursive）由于這些函數(shù)只在自然數(shù)的一部分上有確定的輸出，它們也被稱作部分可計算函數(shù)（partial computable）。

可以證明部分可計算函數(shù)的全體就是使用圖靈機(jī)可以計算的函數(shù)的全體。數(shù)學(xué)上要證明這一點，一方面我們可以通過具體的構(gòu)造證明可以被圖靈機(jī)計算的所有函數(shù)構(gòu)成的集合確實滿足這里1~6的所有公理，這并不困難。而另一方面，我們需要說明使用部分可計算函數(shù)確實可以模擬所有圖靈機(jī)的行為。

為此，我們需要對圖靈機(jī)進(jìn)行編碼。一條形如“(qi, _ , qj , * , ←)”的圖靈機(jī)指令可以看成一個列表，通過上面的討論，我們可以使用一個自然數(shù)來編碼這一條指令。而圖靈機(jī)的所有指令便可以表達(dá)為一個自然數(shù)列表，而這個列表又可以編碼為一個自然數(shù)，于是我們可以用一個自然數(shù)來表示一個圖靈機(jī)，這便是哥德爾數(shù)。不同圖靈機(jī)的哥德爾數(shù)一定不相同，于是我們將圖靈機(jī)按照哥德爾數(shù)從小到大排列起來，依次編號，這就是圖靈機(jī)編號。

我們可以定義這樣一個原始遞歸函數(shù)φ(e, t, x1, … , xk)來模擬圖靈機(jī)運行t步后的狀態(tài)，其中e為圖靈機(jī)編號，φ從e中解碼出圖靈機(jī)的全部指令，用自然數(shù)編碼的列表來模擬紙帶，將(x1, … , xk)作為編號是e的圖靈機(jī)的輸入，模擬該圖靈機(jī)運行t步，最后輸出表達(dá)圖靈機(jī)狀態(tài)以及紙帶信息的多維列表。由于這里的每一步都是可以被明確計算的，不需要使用while循環(huán)，所以φ實際上是一個原始遞歸函數(shù)。最后我們可以定義一個部分可計算函數(shù)Φ(e, x1, … , xk)，它使用while循環(huán)令φ(e, t, x1, … , xk)中的t取遍1, 2, 3, 4, 5, … 直到編號是e的圖靈機(jī)在輸入(x1, … , xk)上停機(jī)，最后輸出紙帶上的結(jié)果。于是Φ(e, x1, … , xk)，作為一個(x1, … , xk)上的函數(shù)，便完全模擬了編號為e的圖靈機(jī)的行為。同時可以看出Φ確實是一個部分可計算函數(shù)。

至此，我們便可以得出結(jié)論，部分可計算函數(shù)的全體就是使用圖靈機(jī)可以計算的函數(shù)的全體。這也與我們的直觀感受完全一致，因為部分可計算函數(shù)可以表達(dá)所有我們可能遇到的編程語句。

對應(yīng)函數(shù)Φ，也一定存在一個圖靈機(jī)，它可以像Φ一樣模擬任何圖靈機(jī)的計算過程，于是我們把Φ稱作通用圖靈機(jī)（universal Turing machine），它就是我們每天使用的電腦，而其他圖靈機(jī)便是電腦上運行的程序或者實現(xiàn)確定功能的芯片，圖靈機(jī)編號便是程序的源碼。同時，證明一個系統(tǒng)有不亞于圖靈機(jī)的計算能力，我們只需要說明它能計算的函數(shù)滿足上述6條公理即可，即系統(tǒng)的底層確實可以實現(xiàn)這6個api。

Kolmogorov 的心結(jié)

圖靈機(jī)可以被編號本身就是一件極其不平凡的事情，這說明圖靈機(jī)和自然數(shù)一樣多。自然數(shù)有無窮多個，我們可以寫的程序，也就是圖靈機(jī)也是無窮多個，這沒有什么問題。然而，所有的無窮都是一樣多的嗎？

假如由0和1組成的無窮序列和自然數(shù)一樣多，也就是說可以像自然數(shù)一樣一個一個排列出來，那么我只需要像上圖一樣，取一個序列，它的第i位和排列出的第i個無窮序列的第i位不一樣，那么這個構(gòu)造出的無窮序列一定和排列出的所有無窮序列不同。這就說明由0和1組成的無窮序列一定是不能被像自然數(shù)一樣排列出來的，也就是說它們比自然數(shù)更多。

事實上，要理解無窮有大有小并不困難。實數(shù)和自然數(shù)誰更多？當(dāng)然是實數(shù)。我們用概率的角度來考慮好了，我們只需要考慮自然數(shù)集合的“長度”和實軸的長度的比值。對于自然數(shù)n，我們可以把它包裹在一個區(qū)間(n-ε/2^n, n+ε/2^n)中，然后把這些區(qū)間加起來，結(jié)果是 ε(2+1+1/2+1/4+1/8+1/16+…)=4 ε。也就是說“自然數(shù)集合的長度”一定是小于4ε的。然而ε可以任意地小，例如0.0001已經(jīng)夠小了，但是我可以讓4ε取0.000000001，只要是個正數(shù)就行。于是“自然數(shù)集合的長度”一定是0，否則我的4ε可以更小，從而得到矛盾。

上面這個討論看似毫無意義，因為自然數(shù)是點，而實數(shù)是線，點表示的數(shù)怎么可能比線表示的數(shù)更多。但事實上，由于有理數(shù)都可以寫成分?jǐn)?shù)p/q的形式，其中p和q都是整數(shù)，[0,1]區(qū)間中的有理數(shù)一定是可以被一個一個排列出來的。上述討論可以完全移植到[0,1]區(qū)間中的有理數(shù)與[0,1]區(qū)間中的實數(shù)上。也就是說在[0,1]區(qū)間中隨便挑一個點，選到有理數(shù)的概率是0！

那這和我們的圖靈機(jī)又有什么關(guān)系呢？事實上，我們可以用二進(jìn)制小數(shù)來表示[0,1]區(qū)間中的點，每一個點都對應(yīng)著一個由0和1組成的無窮序列。而圖靈機(jī)和自然數(shù)一樣多，也就是說和[0,1]區(qū)間上的有理數(shù)一樣多，那么推論便是在所有由0和1組成的無窮序列中，抽到能被圖靈機(jī)“計算”或者說“預(yù)測”的無窮序列的概率是0。

想到這里不免悲從心來，原來我們可以計算的問題是如此之少，連滄海一粟都比不上。因為至少那一粟還有體積，而我們可以“計算”的無窮序列在所有無窮序列面前就是個0。但再仔細(xì)想想，難道事實不就應(yīng)該如此嗎？假如說有一個系統(tǒng)隨機(jī)且均勻地不停產(chǎn)生數(shù)字0和1，它產(chǎn)生的0和1一定是混亂而不可預(yù)測的，所以“它產(chǎn)生的0和1具有特定模式”一定是一個不可能事件，“具有特定模式”不就是意味著能被圖靈機(jī)“計算”嗎？由此，我們獲得了對于隨機(jī)性與概率論更加深刻與本質(zhì)的理解，即完全不能被任何圖靈機(jī)“預(yù)測”的0和1組成的無窮序列可以被認(rèn)為是隨機(jī)的。事實上數(shù)學(xué)家還證明了，這樣的無窮序列滿足“大數(shù)定律”，即若我們統(tǒng)計該序列中0和1出現(xiàn)的頻率，會發(fā)現(xiàn)它一定收斂于1/2（請注意這里不是幾乎處處收斂，而是一定收斂于1/2）。

據(jù)傳Kolmogorov本人對他創(chuàng)立的概率論并不滿意，Kolmogorov覺得一個客觀存在的、固定不變的概率本就是一個非常奇怪的設(shè)定。雖然在初中、高中、以及幾乎所有大學(xué)的課堂上，“隨機(jī)序列”這種詞語一旦說出口，任課老師大概會覺得這個學(xué)生根本沒有入門，連什么是概率都不清楚。但是在他眼里以及大多數(shù)人樸素的觀念里，01110110001000011010就是比01010101010101010101更加隨機(jī)。最終他的學(xué)生Martin-L?f將這樣的想法發(fā)展成一套完整的理論，形成了一種有別于頻率論學(xué)派和貝葉斯學(xué)派的第三種對概率與隨機(jī)性的觀點，Martin-L?f隨機(jī)性。

Martin-L?f 隨機(jī)性解決了“什么樣的序列才是真正的隨機(jī)”的問題，就是用“通過所有可計算的隨機(jī)性檢驗”來定義真正的隨機(jī)序列。它是算法信息論中最嚴(yán)格、最常用的“隨機(jī)性”定義之一。如果說一個序列是 Martin-L?f 隨機(jī)的，等價于它的所有前綴的 Kolmogorov 復(fù)雜度都很高（不可有效壓縮）。

結(jié)語

作者闡釋了通過計算機(jī)可以計算的函數(shù)全體其實就是部分可計算函數(shù)，證明一個系統(tǒng)有不亞于圖靈機(jī)的計算能力只需要說明它滿足6條公理即可。而圖靈機(jī)可以被編號的事實表明，存在大量的問題都是不可被計算的。這本質(zhì)上是人類和計算機(jī)只能處理有限的、離散的信息的體現(xiàn)。在Martin-L?f隨機(jī)性的觀點下，正是從這種局限性中涌現(xiàn)出了概率。

圣塔菲課程

本課程探討計算復(fù)雜性，涵蓋搜索算法、解圖、約簡和普適性等主題。我們探討的問題涵蓋范圍廣泛，從簡單（多項式時間）到困難（NP 完全）再到不可能（不可判定）。

課程主講人 Cristopher Moore 是圣菲研究所的常駐教授。他擁有西北大學(xué)物理學(xué)、數(shù)學(xué)和綜合科學(xué)學(xué)士學(xué)位，以及康奈爾大學(xué)物理學(xué)博士學(xué)位。他撰寫了 150 篇關(guān)于物理學(xué)和計算機(jī)科學(xué)交叉領(lǐng)域的論文，涵蓋量子計算、NP 完全問題中的相變、社交網(wǎng)絡(luò)理論及其結(jié)構(gòu)分析的有效算法等，與Stephen Smale 合著了牛津大學(xué)出版社出版的《計算的本質(zhì)》。

1.

2.

3.

4.

5.

6.

7.