mayaoji的个人博客分享 http://blog.sciencenet.cn/u/mayaoji

博文

计算机算不了的函数是什么样的? 精选

已有 13750 次阅读 2018-1-30 12:39 |个人分类:逻辑学|系统分类:科普集锦| 图灵机, 可计算性, 停机函数

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

马耀基

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

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

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

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

1、函数

先复习一下什么是函数。

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

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

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

2、程序

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

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

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

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

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

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

3、无法计算的函数

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

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

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

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

A、反对角线函数

给所有计算一元函数的程序分配号码,将这些程序记为P1P2P3,……Pn,……,每个程序对应着一个可计算函数。

现在构造反对角线函数dd的定义是这样的:

d(n)=2,如果Pn(n)=1

d(n)=1,如果Pn(n)1,或者Pn(n)无定义。

Pn(n)=1,表示当输入为n时,程序Pn的输出是1。)

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


函数d与任何一个程序所计算的函数都不同。因为n=1时,d(1) P1(1),在n=2时,d(2) P2(2),……,n=m时,d(m) Pm(m)。所以函数d是任何一个程序不能计算的。

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

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

B、程序结束函数(也称图灵机停机函数)

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

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

程序结束函数h,具体来说是这样的:

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

h (m,n)=2,如果程序Pm在输入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就是程序Pt。输入t时,G(t)会结束吗?按定义,如果Pt(t)结束,则h(t,t)=1,则G(t)不结束永远运行。但程序Pt就是程序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,它算的是另一个函数,这个函数在x0时,和y=10/x一样,但x0时,y仍然有取值。如果算的是y=10/x,则x=0时,程序不结束。

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

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


科学花果山

相关文章

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




https://blog.sciencenet.cn/blog-1255140-1097600.html

上一篇:说谎者悖论:从鳄鱼难题到数学证明的极限
下一篇:反对角线:从理发师悖论到计算机的极限
收藏 IP: 219.136.111.*| 热度|

5 黄永义 徐明昆 张忆文 Hyq18936853798 hmaoi

该博文允许注册用户评论 请点击登录 评论 (1 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-3-28 21:09

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部