从可计算性理论理解概率的本质

导语

Kolmogorov使用了三条公理奠定了当今概率论的基础。然而据传，他本人对此并不满意。本文将从可计算性理论的角度向您介绍超越Kolmogorov公理的对于概率论的鲜为人知的全新理解。

关键词：概率论、随机性、图灵停机、Martin-Löf随机性、可计算性

罗浩源（宾夕法尼亚州立大学在读博士）丨作者

万能的上帝可以解出哥德巴赫猜想吗

上帝是万能的吗？大概不是吧。哲学家给出了这样的论述。如果上帝是万能的，那他应该能创造一个自己也举不起来的石头。但如果他自己也举不起来这块石头，他还是万能的吗？或许您会觉得哲学家的这个诡辩荒诞不经，但如果我换一个问法，您会立马意识到其中的价值。

我们写程序时都非常讨厌程序陷入死循环，那么是否存在这样一个全知全能的程序 ，我们输入一个程序源代码的字符串 ，以及打算喂给该程序的输入字符串，它可以自动判断源码所描述的程序在输入字符串上是否会陷入死循环。如果假设这样的程序存在，通过类似于上面关于万能上帝的讨论，我们可以很容易地推出矛盾，从而证伪这个命题。

图灵停机问题的推理过程：

1. 假设存在这样一个全知全能的程序 H，它能判断任意一个程序 P 和输入 I，P 在输入 I 时是否会停机（不会死循环）。

   1. if H(P,I) == "会停机":

      return "是" # 不会死循环

      else:

      return "否" # 死循环

2. 构造一个新程序 D，它的行为如下：

• D 接受一个程序 Q 作为输入。

• D(Q) 的逻辑：

• 用 H(Q, Q) 判断 Q 在输入 Q 时是否会停机。

• 如果 H(Q, Q) 说“会停机”，则让 D(Q) 进入死循环。

• 如果 H(Q, Q) 说“不会停机”，则让 D(Q) 立刻停机。

def D(Q):

if H(Q, Q) == "会停机":

while True: # 死循环

pass

else:

return 0 # 立刻停机

3. 让 D 输入自己 D(D)

• 如果 H(D, D) 说“会停机”，那么根据 D 的定义，D(D) 会死循环（矛盾）。

• 如果 H(D, D) 说“不会停机”，那么根据 D 的定义，D(D) 会立刻停机（矛盾）。

• 也就是说，无论 H 怎么判断，都会产生矛盾。

“判断程序是否陷入死循环”就是大名鼎鼎的停机问题，这个全知全能的程序并不存在就是人们常说的停机问题不可判定。但稍微了解过数学史的读者很快便能意识到，这就是引起第三次数学危机的罗素悖论的变体，而这与哥德尔不完备性定理也有千丝万缕的联系。上面关于停机问题的论述并没有使用任何具体的构造，但却清楚地表明了一个事实，即便计算机解决了当今无数的难题，创造了无尽的财富，总有一些问题是永远没有办法使用计算机解答的，量子计算机也不行。我们称这类问题是不可计算的。作者在后文将会指出，我们能够精确计算的问题其实少得可怜。

事实上，如果这样一个全知全能的程序真的存在，它可以轻松地回答当今困扰无数数学家的难题。例如哥德巴赫猜想：任一大于2的偶数都可写成两个素数之和。

我们只需要写一个程序，其中使用while循环依次枚举大于2的所有偶数，在循环体中依次尝试所有不大于当前偶数的素数组合，看看其中是否有一个组合能满足哥德巴赫猜想的要求。如果某个偶数不能满足要求，使用break语句终止while循环然后输出0，反之就一直计算下去。

若这样的全知全能的程序真的存在，我们只需要用它判断一下上一段中所描述的程序是否会陷入死循环便可以轻而易举地知道哥德巴赫猜想是否正确。哥德巴赫猜想至今仍未被完全证明的事实也从侧面印证了这样的全知全能的程序并不存在，不可计算的问题是很多的。但不可计算并不意味着我们无能为力，在Martin-Löf随机性的观点下，正是从不可计算的局限性中涌现出了概率。

数学上一个程序长啥样

图灵在1936年提出了计算机的理论模型——图灵机。上图便是图灵机的示意图。无穷长的纸带上，每一格可以打点也可以留空，有一个读取写入头在纸带上移动，并修改纸带上的数据。读取写入头有很多不同的状态，以及一系列的指令。例如，在上图中，(qi, _ , qj , * , ←)指令的含义是，若读取写入头当前是“qi”，当前读到了空格“_”，那么将当前状态改为“qj”，在当前空格中写入“*”，最后向左手移动。而在图片所表示的例子中，读取写入头的当前状态是“qk”，读取到的信息是“*”，于是匹配到第二条指令，将当前状态改为“qh”，擦除当前格子中的“*”，最后向右移动。读取写入头有一个最终状态，当达到最终状态后它停止工作，此时我们称图灵机停机，表示计算完成，而纸带上的信息就是计算的结果。

图灵机刻画了人类和计算机的计算过程，是一个相当成功的模型。但若想要研究到底什么问题是可计算的，什么是不可计算的，直接构造图灵机写出指令还是太麻烦了。回想我们在实际编程中是如何操作的，我们把机器语言封装成汇编语言，又把汇编语言封装成其他高级语言，通过代码库的复用简化我们的思维过程。于是数学家将图灵机可以实现的基本操作封装成了如下的5个api。考虑满足如下公理的、输入是有限位自然数、输出是一个自然数的函数的最小集合 C。它们满足：

1. 自增函数在C中。即C中存在一个函数s, s(n)=n+1。

2. 所有的常数函数在C中。即对于任意的m，都存在一个函数cm, cm(x1, …, xk)=m，cm在函数集合C中。

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

4. 函数的复合在C中。即，若g1, … gk 和h在C中，那么h(g1, … , gk)也在C中。

5. 递归函数在C中。即，若g和h在C中，g的输入为k元自然数数组，h的输入为k+2元自然数数组，则在C中存在函数f，满足f(0, x1, … , xk)=g(x1, … xk), 且f(n+1, x1, … xk)=h(n, x1, … xk, f(n, x1, … xk))。

数学家们把这样最小的函数集合C叫做原始递归函数（primitive recursive function），也就是使用这五个api可以组合出的所有运算的全体。这五个“基础api”或者五条公理看似平平无奇，但是千万不要因此小看了原始递归函数，事实上，通过原始递归函数我们可以表达出任何不使用while循环的算法。若您不信，您可以自己动手试试。

通过递归函数，我们可以表达出加法，有了加法，使用递归便有了乘法。通过递归，我们还可以定义减法，只不过a-b在b比a大时输出0。通过递归，我们还可以定义一个函数σ，它在任意非零自然数上输出1，而在0上输出0，于是只需要计算σ(a-b)，便可以比较a和b的大小。从而类似地可以定义布尔运算。而如果f是一个判断函数，当条件满足时输出1，反之输出0，使用乘法，f*g+(1-f)*h，便是一条if-else语句，当f的条件满足时该表达式输出函数g的计算结果，反之则输出h的计算结果。同时通过递归我们还可以定义do循环。

看到这里您或许会问，原始递归函数确实有很强的表达能力，但是各种列表操作它能做到吗？答案是能！通过原始递归函数，我们可以表示出带余数的除法，从而可以通过除法进行因式分解。我们把列表的各个元素藏在自然数的因数中即可。例如2^5*3^8*5^1*7^10，就表示一个(5, 8, 1, 10)的动态列表。

至此，我们可以肯定，所有不使用while循环的算法都可以用一个原始递归函数来表示，同时因为没有使用while循环，原始递归函数都会在有限步之内停止并给出确定的结果，所以原始递归函数都是可计算的（但并非所有可计算函数都是原始递归函数，因为某些使用了while循环的算法也可以给出确定的结果）。没有while循环，我们的api还是不够强大。那么，while循环呢？其实我们只需要再封装一个api或者说在集合 C中再加一条公理：

1. 若一个k+1位输入的函数θ在C中，那么在C中有一个函数ψ(x1, … , xk)，若θ(x1, … xk, i) 在i

于是这样，我们便刻画了while循环。这个新的函数集合比原始递归函数的集合更大，我们称它是μ-递归函数（μ-recursive）由于这些函数只在自然数的一部分上有确定的输出，它们也被称作部分可计算函数（partial computable）。

可以证明部分可计算函数的全体就是使用图灵机可以计算的函数的全体。数学上要证明这一点，一方面我们可以通过具体的构造证明可以被图灵机计算的所有函数构成的集合确实满足这里1~6的所有公理，这并不困难。而另一方面，我们需要说明使用部分可计算函数确实可以模拟所有图灵机的行为。

为此，我们需要对图灵机进行编码。一条形如“(qi, _ , qj , * , ←)”的图灵机指令可以看成一个列表，通过上面的讨论，我们可以使用一个自然数来编码这一条指令。而图灵机的所有指令便可以表达为一个自然数列表，而这个列表又可以编码为一个自然数，于是我们可以用一个自然数来表示一个图灵机，这便是哥德尔数。不同图灵机的哥德尔数一定不相同，于是我们将图灵机按照哥德尔数从小到大排列起来，依次编号，这就是图灵机编号。

我们可以定义这样一个原始递归函数φ(e, t, x1, … , xk)来模拟图灵机运行t步后的状态，其中e为图灵机编号，φ从e中解码出图灵机的全部指令，用自然数编码的列表来模拟纸带，将(x1, … , xk)作为编号是e的图灵机的输入，模拟该图灵机运行t步，最后输出表达图灵机状态以及纸带信息的多维列表。由于这里的每一步都是可以被明确计算的，不需要使用while循环，所以φ实际上是一个原始递归函数。最后我们可以定义一个部分可计算函数Φ(e, x1, … , xk)，它使用while循环令φ(e, t, x1, … , xk)中的t取遍1, 2, 3, 4, 5, … 直到编号是e的图灵机在输入(x1, … , xk)上停机，最后输出纸带上的结果。于是Φ(e, x1, … , xk)，作为一个(x1, … , xk)上的函数，便完全模拟了编号为e的图灵机的行为。同时可以看出Φ确实是一个部分可计算函数。

至此，我们便可以得出结论，部分可计算函数的全体就是使用图灵机可以计算的函数的全体。这也与我们的直观感受完全一致，因为部分可计算函数可以表达所有我们可能遇到的编程语句。

对应函数Φ，也一定存在一个图灵机，它可以像Φ一样模拟任何图灵机的计算过程，于是我们把Φ称作通用图灵机（universal Turing machine），它就是我们每天使用的电脑，而其他图灵机便是电脑上运行的程序或者实现确定功能的芯片，图灵机编号便是程序的源码。同时，证明一个系统有不亚于图灵机的计算能力，我们只需要说明它能计算的函数满足上述6条公理即可，即系统的底层确实可以实现这6个api。

Kolmogorov 的心结

图灵机可以被编号本身就是一件极其不平凡的事情，这说明图灵机和自然数一样多。自然数有无穷多个，我们可以写的程序，也就是图灵机也是无穷多个，这没有什么问题。然而，所有的无穷都是一样多的吗？

假如由0和1组成的无穷序列和自然数一样多，也就是说可以像自然数一样一个一个排列出来，那么我只需要像上图一样，取一个序列，它的第i位和排列出的第i个无穷序列的第i位不一样，那么这个构造出的无穷序列一定和排列出的所有无穷序列不同。这就说明由0和1组成的无穷序列一定是不能被像自然数一样排列出来的，也就是说它们比自然数更多。

事实上，要理解无穷有大有小并不困难。实数和自然数谁更多？当然是实数。我们用概率的角度来考虑好了，我们只需要考虑自然数集合的“长度”和实轴的长度的比值。对于自然数n，我们可以把它包裹在一个区间(n-ε/2^n, n+ε/2^n)中，然后把这些区间加起来，结果是 ε(2+1+1/2+1/4+1/8+1/16+…)=4 ε。也就是说“自然数集合的长度”一定是小于4ε的。然而ε可以任意地小，例如0.0001已经够小了，但是我可以让4ε取0.000000001，只要是个正数就行。于是“自然数集合的长度”一定是0，否则我的4ε可以更小，从而得到矛盾。

上面这个讨论看似毫无意义，因为自然数是点，而实数是线，点表示的数怎么可能比线表示的数更多。但事实上，由于有理数都可以写成分数p/q的形式，其中p和q都是整数，[0,1]区间中的有理数一定是可以被一个一个排列出来的。上述讨论可以完全移植到[0,1]区间中的有理数与[0,1]区间中的实数上。也就是说在[0,1]区间中随便挑一个点，选到有理数的概率是0！

那这和我们的图灵机又有什么关系呢？事实上，我们可以用二进制小数来表示[0,1]区间中的点，每一个点都对应着一个由0和1组成的无穷序列。而图灵机和自然数一样多，也就是说和[0,1]区间上的有理数一样多，那么推论便是在所有由0和1组成的无穷序列中，抽到能被图灵机“计算”或者说“预测”的无穷序列的概率是0。

想到这里不免悲从心来，原来我们可以计算的问题是如此之少，连沧海一粟都比不上。因为至少那一粟还有体积，而我们可以“计算”的无穷序列在所有无穷序列面前就是个0。但再仔细想想，难道事实不就应该如此吗？假如说有一个系统随机且均匀地不停产生数字0和1，它产生的0和1一定是混乱而不可预测的，所以“它产生的0和1具有特定模式”一定是一个不可能事件，“具有特定模式”不就是意味着能被图灵机“计算”吗？由此，我们获得了对于随机性与概率论更加深刻与本质的理解，即完全不能被任何图灵机“预测”的0和1组成的无穷序列可以被认为是随机的。事实上数学家还证明了，这样的无穷序列满足“大数定律”，即若我们统计该序列中0和1出现的频率，会发现它一定收敛于1/2（请注意这里不是几乎处处收敛，而是一定收敛于1/2）。

据传Kolmogorov本人对他创立的概率论并不满意，Kolmogorov觉得一个客观存在的、固定不变的概率本就是一个非常奇怪的设定。虽然在初中、高中、以及几乎所有大学的课堂上，“随机序列”这种词语一旦说出口，任课老师大概会觉得这个学生根本没有入门，连什么是概率都不清楚。但是在他眼里以及大多数人朴素的观念里，01110110001000011010就是比01010101010101010101更加随机。最终他的学生Martin-Löf将这样的想法发展成一套完整的理论，形成了一种有别于频率论学派和贝叶斯学派的第三种对概率与随机性的观点，Martin-Löf随机性。

Martin-Löf 随机性解决了“什么样的序列才是真正的随机”的问题，就是用“通过所有可计算的随机性检验”来定义真正的随机序列。它是算法信息论中最严格、最常用的“随机性”定义之一。如果说一个序列是 Martin-Löf 随机的，等价于它的所有前缀的 Kolmogorov 复杂度都很高（不可有效压缩）。

结语

作者阐释了通过计算机可以计算的函数全体其实就是部分可计算函数，证明一个系统有不亚于图灵机的计算能力只需要说明它满足6条公理即可。而图灵机可以被编号的事实表明，存在大量的问题都是不可被计算的。这本质上是人类和计算机只能处理有限的、离散的信息的体现。在Martin-Löf随机性的观点下，正是从这种局限性中涌现出了概率。

圣塔菲课程

本课程探讨计算复杂性，涵盖搜索算法、解图、约简和普适性等主题。我们探讨的问题涵盖范围广泛，从简单（多项式时间）到困难（NP 完全）再到不可能（不可判定）。

课程主讲人 Cristopher Moore 是圣菲研究所的常驻教授。他拥有西北大学物理学、数学和综合科学学士学位，以及康奈尔大学物理学博士学位。他撰写了 150 篇关于物理学和计算机科学交叉领域的论文，涵盖量子计算、NP 完全问题中的相变、社交网络理论及其结构分析的有效算法等，与Stephen Smale 合著了牛津大学出版社出版的《计算的本质》。

1.

2.

3.

4.

5.

6.

7.