转：数学之误:图灵停机悖论其实是一个数学诡辩

本文作者:内蒙古根河市板业公司:李冕(13644809845) 　　全文如下: 　　图灵是英国的数学家,计算机逻辑的奠基者，许多人工智能的重要方法都源自于这位伟大的科学家。他对计算机的重要贡献在于他提出的早期计算机的雏形图灵机的概念，因此为誉为是人工智能之父. 　　所谓的图灵停机问题是指：存在不存在一个程序比如说P，能够判断出任意一个程序X是否会在输入数据Y的情况下停机？我们不妨设P(X,Y)表示P判断程序是X，数据是Y的结果。如果停机，那么P(X,Y)就输出一个yes。如果不停机，那么P(X,Y)就输出一个no,这就是图灵停机问题. 问这样的程序P存在吗? 　　图灵证明,这样的程序P是不存在的,他用的是反证法,证明如下: 　　假设程序P存在。那么可以根据P设计一个新的程序Q如下： 　　X是任何一段程序的编码： 　　Program Q(X){ 　　m=P(X,X) 　　do while (m=no) 　　… 　　… 　　end do 　　if m=yes then return } 　　这段程序通俗来讲就是：输入任何一段程序X，调用函数P(X,X)并得到返回值m，如果m=no，也就是说根据P的定义，P判断出程序X作用到它自己身上X不存在死循环。那么Q就不停的做do while和end do之间的语句。如果m=yes，我们知道这表示P判断出程序X在X上存在死循环。就返回，结束该函数。 　　我们可以看到，这样定义的函数Q(X)是没有问题的。下面就进入关键时刻了：我们问Q这个程序作用到Q自身的编码上也就是Q(Q)会不会死循环呢？当然我们可以运用强有力的函数P(Q,Q)来计算这个问题。 　　假设Q(Q)会发生死循环，那么P(Q,Q)就会返回yes。然而根据Q函数的定义，把X=Q代入其中会发现由于P(Q,Q)返回的是yes，也就是m=yes，因此Q函数会马上结束，也就是程序Q(Q)没有发生死循环。然而如果假设Q(Q)不发生死循环，那么P(Q,Q)应该返回no,这样根据Q函数的定义，把X=Q代入Q(Q)之中会得到m=no，这样程序就会进入do while循环，而这个循环显然是一个死循环。因而Q(Q)发生了死循环！这又导致了矛盾。 　　无论Q(Q)会不会发生死循环，都会产生矛盾，然而哪里错了呢？答案只能是最开始假设的前提错了，也就是说最开始的假设P(X,Y)能够判断任意程序X在输入Y的时候是否死循环是错误的！也就是说这样的程序P(X,Y)不存在. 　　 图灵证明这个问题其实是运用了康托尔的对角线删除法,下面来介绍一下图灵是如何运用对角线删除法来证明上述命题的: 　　 假设这样的P(X,Y)是存在的。而我们知道程序X本身是可以被编码的。也就是可以为所有的程序进行编号：x1，x2，x3，x4……，而数据Y本身也是这样的编号y1，y2，y3，y4……，因而我们就可以把每一对X和Y的组合排列在一张表上。比如横行表示的是数据Y，而纵行表示的是程序X，这样P(X,Y)的值也就是yes或no就可以写在第X行第Y列的对应位置上，表示P(X,Y)判断出的X作用在输入Y上是否会死循环的结果。比如下面的表就是一个示例： 　　 y1 y2 y3 y4 y5 y6 …… Yn …… 　　x1: yes no no yes yes no …… yes …… 　　x2: no no yes yes no yes …… no …… 　　x3:yes yes no no yes no........ no 　　… ……………………………………… 　　xn: no yes no yes yes no …… yes …… 　　… …………………………………… 　　上表中的每一个行都表示一个确定的程序作用到不同的数据上所得到的结果。比如程序Xn作用在y1,y2,y3,y4,……,Yn，……上给出的结果就是一个序列： 　　no,yes,no,yes,yes,no,……,yes，…… 　　下面我们把上表对角线上的元素挑出来。也就是专门找那些第1行第1列，第2行第2 列，第三行第三列……这样的元素就可以得到一个序列： 　　yes,no,no, …… 　　而根据这个序列我们完全可以构造这样一个反序列： 　　no,yes,yes…… 　　也就是说这个序列在每一个位上都与前一个对角线序列不同！这个序列就称为对角线删除序列。那么问，这个对角线删除序列是否在上表中的某一行上呢？答案是否定的！这个序列必然不在表中。因为它的第一个元素与1,1不同，第二个元素与2,2不同，第三个元素与3,3不同.........所以这个构造出来的对角线删除序列不在表中！ 　　我们完全可以设计出一段程序Q使得Q作用在数据上产生的序列就是对角线删除序列，而对角线删除序列不在表中就意味着程序P并不能判断出程序Q作用在任意输入上是否停机。其实这里的程序Q就是前一节论证停机问题的程序Q。用对角线删除的证明方法来看究竟哪里出错了呢？错误就出在我们假设程序P能够得到这样一张完整的表，这张表对所有的程序计算能得到是否停机的答案。 　　看完了上述图灵的证明,接下来就转入正题:为什么说图灵的这个证明是一个数学诡辩?因为图灵用对角线删除法来证明这个命题是一个逻辑上的错误,图灵首先假设将所有的程序x作用到所有的数据y上的结果排列成为一个序列表,但这个序列表却是无序排列的,完全没有秩序的乱排列,这样能够将所有的程序作用在所有的数据上的所有结果一个不漏的全都排列出来吗?显然是不能的.举例来说:自然数集合N,如果这样排列:{1,2,3,4,..........},这样是可以将所有的自然数一个不漏的全排列出来的,但是如果是无序的乱排列,排成这个样子:{3,17,9,852,143,2,58......... },这样能保证将所有的自然数一个不漏的全排列出来吗?显然不能. 　　也就是说,因为图灵无法将所有的程序作用在所有的数据上的所有结果一个不漏的全排列出来,所以才使得他能够轻易的用对角线的方法构造出来一个不在表中的新的序列,按照这个想法,只要是能够创造出来一种方法,能够将所有的程序作用在所有的数据上的所有结果一个不漏的全都排列成为一个全序表,那么图灵就无法再用对角线法来构造新的序列了. 　　而这种构造全序的方法,恰恰就是对角线法:既然图灵是用的对角线的方法构造出来了一个不在图表中的新的序列,那么我就反其道而行之,运用对角线法构造全体序列,构造方法如下: 　　首先:程序x作用在数据y上的输出结果只有两个:一个是yes,表示的是停机,一个是no,表示的是不停机,为了方便起见,我们将yes和no用两个数字来代替:用1代表no,表示不停机,用0代表yes,表示停机,也就是说,如果程序x作用在y上的结果是不停机就输出一个1,反之就输出一个0.下面我们就用1和0两个数字来构造出来全体序列,方法如下: 　　首先来做一个数学模型:以原点O为起点向正方向画一条无限延长的射线,将所有的数据:y1,y2,y3,y3,y4..........依次的排列的在射线的单位长度上,然后再以原点O向下做一条无限延长的射线,将所有的程序:x1,x2,x3,x4..........也依次的排列在这条射线的单位长度上,这就相当于是一个平面直角坐标系的第四象限.然后再从原点O处同样引出来一条无限延长的射线,使得该射线与两条射线呈45度角(就是第四象限的角平分线,也即是对角线),这样,x1与y1的交点(1,1),x2与y2的交点(2,2),x3与y3的交点(3,3)..........就全都交在这条对角线上.我们假设在(1,1),(2,2),(3,3),(4,4)..........的每一个点上都放有一个小盒子,每个盒子里都放着1和0两个数,称(1,1)点处的盒子为J1盒,(2,2)点处的盒子为J2盒,(3,3)点处的盒子为J3盒..........(J的意思就是程序x作用在数据y上的结果). 　　下面开始构造全序列:首先我们从J1,J2,J3,J4..........的每一个盒子中全都拿出来一个0,这样就构成了一个无穷序列:0,0,0,0,0,0,0...........,这个序列代表的是程序x1作用在数据y1,y2,y3,y4,y5.......上的结果全都是0. 　　 接下来构造程序x2作用在所有数据上的结果:从J1盒中拿出来一个1,其余的所有盒子中全都拿出来一个0,这样就构造出来了程序x2作用在所有数据上的结果为:1,0,0,0,0,0,0........... 　　 我们将上述的两个序列称为是J1级序列,然后在J1级序列的基础上构造J2级序列:构造方法为:令J1=0,J2=1,其余的所有数位全都等于0,构造出来如下的序列:0,1,0,0,0,0,0,0............,这个序列代表的是程序x3作用在所有数据上的输出结果,然后,再令J1=1,J2=1,其余所有数位上的数全都等于0,得到如下的数列:1,1,0,0,0,0,0,0,0..........,这个序列代表的是程序x4作用在所有数据上的输出结果. 　　 在此解释一下:在构造J2级序列的时候为什么不让J2=0?因为如果令J2=0,会和J1级序列重复,例如:令J1=0,J2=0,其余的所有数全都为0,那么得到的序列其实就是0,0,0,0,0.........,它在J1级序列中. 　　 由此我们构造出来了两个J1级序列,两个J2级序列,排成下表如下: 　　 y1 y2 y3 y4 y5 y6 y7 y8 y9.......... 　　 x1: 0 0 0 0 0 0 0 0 0 .......... 　　 x2: 1, 0 0 0 0 0 0 0 0 .......... 　　 x3: 0 1 0 0 0 0 0 0 0 .......... 　　 x4: 1 1 0 0 0 0 0 0 0 ........... 　　 下面我们来构造J3级序列:方法是将x1,x2,x3,x4序列的J3位置全都变成为1,其余数位的数不变,如下: 　　 x5: 0 0 1 0 0 0 0 0 0.......... 　　 x6: 1 0 1 0 0 0 0 0 0.......... 　　 x7: 0 1 1 0 0 0 0 0 0........... 　　 x8: 1 1 1 0 0 0 0 0 0........... 　　 当然,你会发现如果上述序列中的J3如果等于0,它依然还是J1级和J2级的四个序列,所以J3级的序列共有4个. 　　接下来构造J4级的序列,J4级的序列共有8个,也就是将已经构造好的J1级,J2级,J3级的8个序列的J4位置全都变成1,其余数位的数不变,如下: 　　 x9:0 0 0 1 0 0 0 0 0......... 　　x10:1 0 0 1 0 0 0 0 0......... 　　x11:0 1 0 1 0 0 0 0 0......... 　　x12:1 1 0 1 0 0 0 0 0........ 　　x13:0 0 1 1 0 0 0 0 0......... 　　x14:1 0 1 1 0 0 0 0 0.......... 　　x15:0 1 1 1 0 0 0 0 0......... 　　x16:1 1 1 1 0 0 0 0 0........ 　　 介绍到这里,我想大家也就应该知道如何用对角线的方法来构造所有程序作用在所有数据上的所有结果的全序了:也就是说:如果构造J5级序列,就将前J4级已经构造完成的16个序列的J5位置全都变成1,这样就得到16个J5级的序列,如果构造J6级的序列,就将前J5级的32个序列的J6位置全都变成1,这样就又得到32个J6级的序列........按照这个规律,我们就知道在全序中,J1级的序列有两个,J2级的序列有两个,J3级的序列有2^2=4个,J4级的序列有2^3=8个,J5级的序列有2^4=16个,J6级的序列有2^5=32个......Jn级的序列有2^(n-1)个...... 　　所以,只要是严格的按照这种对角线的方法,就可以构造出来所有程序作用在所有数据上的所有结果的全序列出来,也就是说,任意的一个序列都可以在这个对角线全序列中查找出来,举例来说:如何查找这个序列:no,no,yes,no,yes,no,no.........?我们将上述的英文字母用0和1来代替,就是:1,1,0,1,0,1,1.........,首先,我们在J1级序列中可以查找到1,0,0,0,0,0,0..........这个序列,然后运用对角线的方法可以在J2级序列中查找到1,1,0,0,0,0,0,0..........这个序列,由于第三位是0,所以这个序列仍然是在J2级之中的原序列上,第四位是1,便可以在J4级序列中查找到1,1,0,1,0,0,0,0..........这个序列,第5位是0,则空过去J5级序列,第6位是1,则在J6级序列中可以查找到1,1,0,1,0,1,0,0,0,0,0............这个序列..........,总之,若某一序列中总共有n位,则必可以在Jn级序列中查找得到. 　　 构造完了全体序列,再来看一下图灵的证明还有效吗?图灵先假设存在一个程序P能够判断出来任意一个程序X会在输入数据Y的情况下是否会停机,然后图灵假设将所有程序的输出结果列成一个表,最后用对角线的方法构造出来了一个新的序列,声称这个序列不在所列的表中,并做一新程度Q作用在这个新序列上,所以图灵下结论说:程序P不能判断这个新程序是否会在输入数据Y的情况下停机还是不停机. 　　 但现在看一看这个用对角线法构造出来的全序表,就会知道图灵的证明是不成立的,因为无论是用对角线法构造出来的正序列还是反序列,都能在这个全序表中查找得到,比如说图灵用对角线的方法得出来的正序列是:0,1,0,0,1,1,0.........,反序列是1,0,1,1,0,0,1........,这个正序列和反序列都能在全序表中查找得到,所以说图灵的证明结论是不成立的. 　　 最后说一下,本文的标题是<<图灵停机悖论其实是一种数学诡辩>>,从图灵的证明来看,这的确是一种数学诡辩,但从图灵的证明的本意来看,将它定义为是数学诡辩也许并不恰当,因为这个证明并不是图灵刻意制造出来的诡辩,而是因为图灵对无穷的理论存在误解而造成的,最基本的原因还是在于图灵不知道如何来构造全序表,所以,如果你懂得如何来构造全序表,就不会有上述的证明结论了.