來源：集智俱樂部

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

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

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

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

上帝是萬能的嗎？大概不是吧。哲學(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)造，但卻清楚地表明了一個事實(shí)，即便計(jì)算機(jī)解決了當(dāng)今無數(shù)的難題，創(chuàng)造了無盡的財(cái)富，總有一些問題是永遠(yuǎn)沒有辦法使用計(jì)算機(jī)解答的，量子計(jì)算機(jī)也不行。我們稱這類問題是不可計(jì)算的。作者在后文將會指出，我們能夠精確計(jì)算的問題其實(shí)少得可憐。

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

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

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

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

圖靈在1936年提出了計(jì)算機(jī)的理論模型——圖靈機(jī)。上圖便是圖靈機(jī)的示意圖。無窮長的紙帶上，每一格可以打點(diǎn)也可以留空，有一個讀取寫入頭在紙帶上移動，并修改紙帶上的數(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ī)，表示計(jì)算完成，而紙帶上的信息就是計(jì)算的結(jié)果。

圖靈機(jī)刻畫了人類和計(jì)算機(jī)的計(jì)算過程，是一個相當(dāng)成功的模型。但若想要研究到底什么問題是可計(jì)算的，什么是不可計(jì)算的，直接構(gòu)造圖靈機(jī)寫出指令還是太麻煩了?；叵胛覀冊趯?shí)際編程中是如何操作的，我們把機(jī)器語言封裝成匯編語言，又把匯編語言封裝成其他高級語言，通過代碼庫的復(fù)用簡化我們的思維過程。于是數(shù)學(xué)家將圖靈機(jī)可以實(shí)現(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可以組合出的所有運(yùn)算的全體。這五個“基礎(chǔ)api”或者五條公理看似平平無奇，但是千萬不要因此小看了原始遞歸函數(shù)，事實(shí)上，通過原始遞歸函數(shù)我們可以表達(dá)出任何不使用while循環(huán)的算法。若您不信，您可以自己動手試試。

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

看到這里您或許會問，原始遞歸函數(shù)確實(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ù)來表示，同時因?yàn)闆]有使用while循環(huán)，原始遞歸函數(shù)都會在有限步之內(nèi)停止并給出確定的結(jié)果，所以原始遞歸函數(shù)都是可計(jì)算的（但并非所有可計(jì)算函數(shù)都是原始遞歸函數(shù)，因?yàn)槟承┦褂昧藈hile循環(huán)的算法也可以給出確定的結(jié)果）。沒有while循環(huán)，我們的api還是不夠強(qiáng)大。那么，while循環(huán)呢？其實(shí)我們只需要再封裝一個api或者說在集合 C中再加一條公理：

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

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

可以證明部分可計(jì)算函數(shù)的全體就是使用圖靈機(jī)可以計(jì)算的函數(shù)的全體。數(shù)學(xué)上要證明這一點(diǎn)，一方面我們可以通過具體的構(gòu)造證明可以被圖靈機(jī)計(jì)算的所有函數(shù)構(gòu)成的集合確實(shí)滿足這里1~6的所有公理，這并不困難。而另一方面，我們需要說明使用部分可計(jì)算函數(shù)確實(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ī)運(yùn)行t步后的狀態(tài)，其中e為圖靈機(jī)編號，φ從e中解碼出圖靈機(jī)的全部指令，用自然數(shù)編碼的列表來模擬紙帶，將(x1, … , xk)作為編號是e的圖靈機(jī)的輸入，模擬該圖靈機(jī)運(yùn)行t步，最后輸出表達(dá)圖靈機(jī)狀態(tài)以及紙帶信息的多維列表。由于這里的每一步都是可以被明確計(jì)算的，不需要使用while循環(huán)，所以φ實(shí)際上是一個原始遞歸函數(shù)。最后我們可以定義一個部分可計(jì)算函數(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í)是一個部分可計(jì)算函數(shù)。

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

對應(yīng)函數(shù)Φ，也一定存在一個圖靈機(jī)，它可以像Φ一樣模擬任何圖靈機(jī)的計(jì)算過程，于是我們把Φ稱作通用圖靈機(jī)（universal Turing machine），它就是我們每天使用的電腦，而其他圖靈機(jī)便是電腦上運(yùn)行的程序或者實(shí)現(xiàn)確定功能的芯片，圖靈機(jī)編號便是程序的源碼。同時，證明一個系統(tǒng)有不亞于圖靈機(jī)的計(jì)算能力，我們只需要說明它能計(jì)算的函數(shù)滿足上述6條公理即可，即系統(tǒng)的底層確實(shí)可以實(shí)現(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í)數(shù)和自然數(shù)誰更多？當(dāng)然是實(shí)數(shù)。我們用概率的角度來考慮好了，我們只需要考慮自然數(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ε可以更小，從而得到矛盾。

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

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

想到這里不免悲從心來，原來我們可以計(jì)算的問題是如此之少，連滄海一粟都比不上。因?yàn)橹辽倌且凰谶€有體積，而我們可以“計(jì)算”的無窮序列在所有無窮序列面前就是個0。但再仔細(xì)想想，難道事實(shí)不就應(yīng)該如此嗎？假如說有一個系統(tǒng)隨機(jī)且均勻地不停產(chǎn)生數(shù)字0和1，它產(chǎn)生的0和1一定是混亂而不可預(yù)測的，所以“它產(chǎn)生的0和1具有特定模式”一定是一個不可能事件，“具有特定模式”不就是意味著能被圖靈機(jī)“計(jì)算”嗎？由此，我們獲得了對于隨機(jī)性與概率論更加深刻與本質(zhì)的理解，即完全不能被任何圖靈機(jī)“預(yù)測”的0和1組成的無窮序列可以被認(rèn)為是隨機(jī)的。事實(shí)上數(shù)學(xué)家還證明了，這樣的無窮序列滿足“大數(shù)定律”，即若我們統(tǒng)計(jì)該序列中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ī)性的觀點(diǎn)，Martin-L?f隨機(jī)性。

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

結(jié)語

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

閱讀最新前沿科技趨勢報(bào)告，請?jiān)L問歐米伽研究所的“未來知識庫”

https://wx.zsxq.com/group/454854145828

未來知識庫是“ 歐米伽 未來研究所”建立的在線知識庫平臺，收藏的資料范圍包括人工智能、腦科學(xué)、互聯(lián)網(wǎng)、超級智能，數(shù)智大腦、能源、軍事、經(jīng)濟(jì)、人類風(fēng)險(xiǎn)等等領(lǐng)域的前沿進(jìn)展與未來趨勢。目前擁有超過8000篇重要資料。每周更新不少于100篇世界范圍最新研究資料。 歡迎掃描二維碼或訪問https://wx.zsxq.com/group/454854145828進(jìn)入。