计算机算不了的函数是什么样的？

马耀基

现在人工智能很热，人们在争论计算机会不会有一天真正具有智慧，超越人类。我们目前还不知道这个问题的答案，但确实知道计算机有很多事情做不了，就连有的函数计算机都算不了。不是人类能力有限设计不出程序来算它们，而是在理论上这些函数就是无法计算的。（可计算，可用计算机计算，可用程序计算，这些概念在本文是同一个意思。）（注释1）

插一句，说起无法计算的函数，我想起一道数学题：请写出一个无法画出图像的函数。（注释2）开始觉得神奇，竟然有这样的函数？看了答案后觉得很简单。这里说的不能计算的函数也是一样，看似不可思议，其实很容易理解这些函数为什么不可计算，甚至无需懂得编程，当然第一个人想到这些函数很困难。

举个例子。我们要画一棵树，使得这棵树和世界上所有的树都不一样。假设所有的树都是绿色的，我们只要把它画成黄色的就行了。但用这种方法，你要知道现有的树共同特征是什么。但就算对树一无所知，理论上我们也知道能画出一棵与众不同的树。我们把全部的树进行编号，然后这样设计这棵新树：它在高度上跟1号树不同，叶子数量跟2号不同，树枝长短跟3号不同，……，总之它和每一棵树都最少有一个地方不同。同样，是否存在不能计算的函数呢？回答这个问题我们无需知道具体的可计算的函数长什么样，只要能设计出和每个可计算函数都不同的函数就行了。我们能画出不同的树，是因为画上的树比真实的树多，与此类似，我们能找到不可计算的函数，本质上是因为函数比程序多。

这篇文章主要的目的是介绍两个不能计算的函数，并且说明它们为什么不能计算。

1、函数

先复习一下什么是函数。

y=x+1，z=x+y，两者都是函数，前者是一元函数，x是自变量，y是因变量。后者是二元函数，其中x、y是自变量，z是因变量。为什么它们是函数呢？因为自变量的值确定时，因变量有唯一的值与之对应，比如y=x+1中，当x=1时，y=2，当x=2时，y=3，而函数z=x+y在x=2，y=3时，z=5。在函数中，自变量的值确定了，允许因变量不取任何值，但不允许因变量的取值超过一个。比如函数y=10/x，当x=0时，y不取任何值，这时说函数在x=0处没有定义。x²+y²=1，这个方程不是以x为自变量的函数，因为x=0时，对应的y有1和-1两个值，同样它也不是以y为自变量的函数。

什么是函数？如果当自变量的值确定时，因变量有0个或1个值与之对应，那这些变量间的关系就构成了函数。自变量只有1个时，就是一元函数，两个时就是二元函数，由此类推。

无法计算的函数，是指不存在这样的程序：当输入自变量的值时，程序总是输出这个函数的因变量的值。

2、程序

一个计算函数y=x+1的程序，就是输入x的值，输出y的值，即如果输入2，它就输出3，如果输入5，它就输出6。如果计算的是二元函数，输入的是两个数，输出的结果还是一个数。

有些程序是不会结束的，它陷入死循环，永远运行下去。比如有一个程序，当输入数字小于10时，它将这个数字加1，然后输出，如果输入的数字大于或等于10，它就不停地进行加1运算，永远不停下来。那这个程序计算的是这个函数：当x<10，y=x+1。当x>=10时，y无定义。

每个程序都计算一个函数。当函数有定义时，程序输出函数值，当没有定义时，程序永远不结束。（注释3）

我们给所有的计算机程序分配号码（或叫编码），这些号码都是自然数。就像每个人都有不同的身份证号码一样，每个程序也有不同的号码。这里编码的不单是指现在世界上存在的所有程序，而是指理论上所有可能的程序，这样的程序数量显然是无限的。（注释4）

每个程序都可以分配不同的号码，看上去是显而易见的事情。实际上并非如此，比如我们就无法给每个实数分配号码，因为实数的数量太多了。程序能够编码，这是需要严格的证明的。这里省略证明，我们直接接受这个结论。

因为所有的程序都是可以编码的，所以所有计算一元函数的程序也可以编码。我们把计算一元函数的程序称为一元程序。

3、无法计算的函数

我们这里构造两个无法计算的函数，一个是反对角线函数，一个是程序结束函数。思路大概这样：

给所有一元程序编码，这些程序对应了所有能计算的一元函数。因为按前面的定义，能计算的函数就是能用程序计算的，而所有的一元程序都在这里了，所以可计算的一元函数也全在这里。构造一个函数，这个函数与任意一个可计算的一元函数，都最少一个在某一个输入值时输出不同。这个函数叫反对角线函数。反对角线函数和所有可计算的函数不同，所以是不可计算的。

另一个是程序结束函数，它能判断任一个程序在任一个输入下是否结束。程序结束函数是无法计算的。有两种证明方法。1、如果程序结束函数能够用程序计算，那反对角线函数就能计算。2、如果程序结束函数能够用程序计算，那就能设计出一个程序，当这个程序把自己的号码作为输入时，会出现矛盾。

下面具体讨论这两个函数。为了简单，我们这里考虑的函数，变量都是自然数。

A、反对角线函数

给所有计算一元函数的程序分配号码，将这些程序记为P₁，P₂，P₃，……P_n，……，每个程序对应着一个可计算函数。

现在构造反对角线函数d，d的定义是这样的：

d(n)=2，如果P_n(n)=1，

d(n)=1，如果P_n(n)≠1，或者P_n(n)无定义。

（P_n(n)=1，表示当输入为n时，程序P_n的输出是1。）

函数d的值总是和下表对角线中的不同，所以叫反对角线函数。

函数d与任何一个程序所计算的函数都不同。因为n=1时，d(1) ≠P₁(1)，在n=2时，d(2) ≠P₂(2)，……，n=m时，d(m) ≠P_m(m)。所以函数d是任何一个程序不能计算的。

还可从另一个角度思考，如果d是可计算的将导致矛盾。假设它是可计算的，则计算它的程序必然分配有号码，假设是s，则函数d就是程序P_s计算的函数，P_s(s)的值是什么？按照定义，如果P_s(s)=1，d(s)≠1，但程序d就是程序P_s，所以矛盾。同样，如果P_s(s) ≠1，也有矛盾。

这里的证明关键是程序可以用自然数编码，如果这个条件不成立，证明就无效了。因为定义d(n)的值时，要用到P_n(n)的值，这需要先给程序分配号码才知道P_n是什么。

B、程序结束函数（也称图灵机停机函数）

反对角线函数为什么不能计算呢？看上去似乎是可以计算的，先判断P_n(n)是否有定义。如果P_n(n)无定义，则d(n)=1，如果P_n(n)有定义，就运行程序P_n，看输入为n时P_n的输出是多少，然后根据规则给d(n)赋值。

困难在于判断P_n(n)是否有定义，即输入为n时，程序P_n是否结束。如果能设计出一个判断程序，对任意的n它都能判断P_n(n)是否结束，则反对角线函数d就是可计算的。因为我们知道函数d无法计算，所以这样的程序是不存在的。这个（不存在的）判断程序所对应的函数是程序结束函数，也叫图灵机停机函数，它是不可计算的。

程序结束函数h，具体来说是这样的：

h (m,n)=1，如果程序P_m在输入n时，最终会结束。

h (m,n)=2，如果程序P_m在输入n时，永远不会结束。（注释5）

我们还可以从另一个角度思考这个问题。

可以证明，如果存在计算函数h的程序H，则我们能构造出一个程序G，当程序G把自己的号码作为输入时会出现矛盾。

程序G是这样的。

输入m，程序G运行程序H(m,m)，如果H(m,m)输出1，则G永远不结束，如果如果H(m,m)输出2，则G结束。

程序G是计算一元函数的，所以G也有一个号码，假设这号码是t，即程序G就是程序P_t。输入t时，G(t)会结束吗？按定义，如果P_t(t)结束，则h(t,t)=1，则G(t)不结束永远运行。但程序P_t就是程序G，矛盾。同理，h(t,t)=2时，也会导致矛盾。所以程序G不存在，因此程序H不存在。

注释：

1、这篇文章说的计算机是指图灵机，我们现在所用的计算机本质上都是图灵机。按照丘奇图灵命题，可计算函数和图灵机可算的函数这两个概念是等价的。

2、这样的函数很多，比如狄利克雷函数：当x是有理数时，y=1，当x是无理数时，y=0。

3、假设有一个程序，当输入x不等于0时，它输出y=10/x的值，当输入0时，输出“输入错误”。严格来说，它算的不是y=10/x，它算的是另一个函数，这个函数在x≠0时，和y=10/x一样，但x≠0时，y仍然有取值。如果算的是y=10/x，则x=0时，程序不结束。

4、不同的程序，功能可以是相同的。比如程序A，对输入的变量先加1，再加2，然后将结果输出。程序B则是先加2，再加1。程序A和B是不同的，所以它们分配到的号码是不同的，但是功能相同。

         5、有人可能会疑惑，当输入为(m,n)的时候，判断程序将m解码成相应的程序，然后再判断这个程序在输入n时是否结束，这样的判断程序H为什么不能存在呢？假设这样的判断程序存在，它在判断P_m(n)是否结束时，有时候要运行P_m(n)，如果P_m(n)永远不结束，程序H不知道它暂时还没算完，还是永远算不完，因此程序H只好继续等待，什么也不输出。因此程序H计算的肯定不是函数h，因为函数h对任意的n都有定义。

科学花果山

相关文章

从理发师悖论到计算机的极限