图灵的停机问题及其对角线证法研究 摘要：停机问题是计算机科学领域最经典的问题之一通过对康托尔对角线法、图灵关于停机问题不可解的对角线证法以及判定程序证法的深入分析，揭示了判定程序证明的本质，指出了在不影响判定程序设计初衷（即拥有对所有其他程序是否停机的判定功能）的前提下，该证明是否定不了这样的判定程序存在的同时揭示了对角线证明方法的根本缺陷和谬误关键字：康托尔，对角线；停机问题；图灵；不可解问题1 引言计算机算法和计算复杂性理论是计算机科学中最重要的组成部分[1]根据计算复杂性理论[12]，自然界和科学理论上的所有问题，可以分为三大类：多项式问题，即可以在多项式时间内得到解答的问题；指数型问题，即可以在指数型时间内得到解答的问题；不可解问题，无论花多少时间，都不可能得到问题的解答[1] [3]对前两类问题，我们可以很容易找到确切的例子来进行说明，但对于最后一类，我们则很难找到具体的例子来说明这个例子就是不可解问题这里请注意，不可解问题与问题本身无解是两个不同的概念例如，我们可以很容易地设计出一个方程，使得该方程无解，我们也能很容易地判断该方程无解。
而不可解问题则指的是，问题本身可能是有解的，只是我们可能无论花多长时间都得不到这个解例如，停机问题就被证明是不可解的[10]，著名的3x+1问题到目前为止亦被认为是不可解的[2] 所谓停机问题指的是：任给一个程序f和一个输入x，是否存在一个判断程序P能判断f对x的计算是否停止？停机问题最先是由计算机科学史上最伟大的天才阿兰-图灵提出来的，著名的被称做计算机之父的冯-诺依曼曾说，图灵才是真正的计算机之父图灵首先提出了停机问题并率先用对角线法证明：停机问题是不可解的自图灵之后，停机问题得到了广泛的研究，关于其不可解性，有两种不同的权威经典证明一个就是图灵的对角线证法，另一种证明方法是，通过设计判定程序来证明停机问题的不可解然而，图灵的对角线证法受到了质疑，不少人认为，这一证明实际上是存在逻辑问题的但判定程序证明法则一直被认可并且，这两种证明一直被大量的沿用引用本文通过详细分析这两个证明过程，包括对角线方法的历史，指出它们的根本缺陷或局限性2 康托尔与对角线方法 谈到停机问题，不能不提到集合理论的发明者康托尔及其对角线法康托尔是用对角线法证明全体实数的个数大于全体自然数的个数的这个方法影响非常深广，直到后来的图灵停机问题、哥德尔定理其实都是该方法的不同延伸。
大家知道，康托尔的主要贡献，就是他的无穷集合理论[8]，无穷集合理论是建立在一一对应的思维方式上的注意一一对应本身只是一种思维方式，并无实质价值若不是他用对角线法将无穷集合分级，那一一对应就是无聊的了，因为那样的活，所有无穷集合都是一一对应的也就是说，推翻了对角线法，就相当于推翻了康托尔的整个理论大厦，包括他的一一对应理论康托尔在研究无穷集合的时候，富有洞察性地看到了对无穷集合的大小问题[5]，我们不能再使用直观的“所含元素的个数”来描述，于是他创造性地将一一对应引入进来，两个无穷集合“大小”一样当且仅当它们的元素之间能够构成一一对应这是一个非常直观的概念，一一对应嘛，当然个数相等了，是不是呢？然而这同时就是它不直观的地方了对于无穷集合，我们日常的所谓“个数”的概念不管用了，因为无穷集合里面的元素个数本就是无穷多个例如，我们说自然数集合能够跟偶数集合构成一一对应，从而自然数集合跟偶数集合里面元素“个数”是一样多的怎么可能？偶数集合是自然数集合的真子集，所有偶数都是自然数，但自然数里面还包含奇数呢，说起来应该是二倍的关系吧？不是！我们只要这样来构造一一对应：1 2 3 4 …2 4 6 8 …用函数来描述就是 f(n) = 2n。
检验一下是不是一一对应的？不可思议对吗？用这种一一对应的手法还可以得到很多惊人的结论，如一条直线上所有的点跟一个平面上所有的点构成一一对应（也就是说复数集合跟实数集合构成一一对应）[6]以致于连康托尔自己都不敢相信自己的眼睛了，这也就是为什么他在给戴得金的信中会说“我看到了它，却不敢相信它”的原因然而，除了一一对应之外，还有没有不能构成一一对应的两个无穷集合呢？有实数集合就比自然数集合要“大”，它们之间实际上无法构成一一对应这就是康托尔的对角线方法要解决的问题证明实数的个数比自然数多，等价于证明实数集不可列，那么实数为什么不能与自然数建立一一对应呢？康托尔的证明如下[7]： 假定（0，1）之间的实数可列，全部列出来如下： 第一个数记为：A1=0.A11A12A13… 第二个数记为：A2=0.A21A22A23… 依此类推，Aij代表列出来的第i个数的第j位小数，是个0到9之间的整数同时，左边与这个数列一一对应的是全体自然数：1,2,3，……n……下面构造一个属于（0，1）的实数B=0.B1B2B3…，不等于所列出的任何一个只要使B1不等于A11（这样B就不等于A1），B2不等于A22（这样B就不等于A2）…依此，Bi不等于Aii…这样构造的数B是（0，1）中的实数而没有被列出来，于是实数不可列。
我们认为，此证明具有大问题第一，是逻辑上的问题，当他试图构造一个完全不一样的实数的时候，这一试图本身就与前面已经列出了“所有”的实数相矛盾，或者说，这一试图本身的前提是，前面并没有完全列出“所有”的实数若是在有穷领域，你当然可以通过这样的方式来反证，因为有穷领域是很直观的、看得很清的但请注意这是在无穷领域，跟有穷领域的思维方式是不一样的逻辑上无穷领域只要包含了“所有”，你就无法再构建“新的”了这个如同下述问题，上帝能制造一块连他自己都搬不动的石头吗？此问题常被用来“证明”不存在万能的上帝但因小前提已假设了结论（“自己都搬不动”），故这样的证明是无聊的如同“上帝能搬动一块连他自己都搬不动的石头吗？”一样的无聊，为了避免后者明显的荒谬可笑，将其中之一的“搬动”改成了“制造”，但本质是一样的你既然假定了上帝万能（无穷），你就不能再在其他前提表述中暗含上帝不能请注意，从逻辑上，万能（无限能）是压倒一切的，正如康托尔那个假设包含了“所有”本身就意味着压倒了一切一样第二，他的对角线法是建立在假定宽和高严格相等的前提下，而在无穷领域，这样的假设是有问题的即使是同级无穷大，这样的假设也说不过去因为你是要构造一个具体的“对角线数”，以两个无穷领域的元素个数严格相等为前提基础来构建一个有穷领域的具体的数，逻辑上是站不住脚的，因为有穷领域的任何常数个数等同于无穷领域的0个数。
他用增加了一行来反证原假设不成立，就好像是在说，无穷大甲比无穷大乙多一个，这样的说法无疑是荒谬的换句话说，康托尔的对角线法，相当于主张如下不等式成立：∞+1 > ∞，而这样的不等式显然是错误的并且，直觉上，他那个列表的高明显大于宽，否则实数就不连续了，也就是说不包含全部了而为了使宽等于高，注意这里因为要构造一个具体的“对角线数”，宽和高就必须严格相等，为了达到这一目的，惟一的方法就是补零而一旦补零，其潜在的含义就是，那个列表并没有包含全部的实数第三，他那个列表假定左边是全部的自然数，与右边全部的实数一一对应既然右边他假定实数全部列出，然后构建一个新的实数来否决这个假定，那我左边为什么不能这样做呢？假定左边的自然数也全部列出来了，这个时候，若按照这个荒谬的对角线法，我们将自然数全部用二进制表示同样，这个时候，直觉上，或者说按照有限领域的理解，高明显大于宽，解决的办法是左边全部补零，这样一来，问题来了，我们也可以在对角线上（按取反）构建一个与前面所有自然数都不相同的自然数总之，由于左边的全部自然数的宽和高也都是无穷的，因而也可以用对角线法予以否定请注意，在宽和高的关系上，左边的自然数和右边的实数是有一定不同的，但你不能以此不同为根据来认定左边无对角线。
而右边有对角线，否则就意味着你是前提里面包含了结论（自然数可数而实数不可数的结论）第四，我们再从另一个角度来看康托尔证法的荒谬我们假定右边那个阵列列出了全部的小数，并且是从小到大排序，第一个小数各位全部是0，“最后”一个小数各位全部是9，中间无缝连续请注意，你不能否定我这个假设，若是你认为我这个假设不成立，那就意味着你的前提里面包含了结论（不可列的结论）所以，到目前为止，我这个假设没有任何问题此时你能不能找到一个不在这个阵列当中的小数呢？毫无疑问不能那么，康托尔为什么能构建出这样一个小数呢？关键是他设想了一条荒谬的根本不存在的对角线在有穷领域，对角线必须是宽和高严格相等而在无穷领域，宽和高相等的含义是什么呢？答案是：宽等于高是相等，宽等于高加1和高等于宽加1其实也是相等的也就是说，在无穷领域，根本不存在一条确定的对角线，若一定要说有对角线，那对角线也是不确定的用不存在或不确定的对角线来构造一个确定的小数无疑是荒谬的第五，我们再来从有穷领域看看康托尔对角线法的诡辩性任何一个宽和高也就是行和列相等的方阵，我们假定其每一行都不相同那么，这样的方阵永远不可能包含用那些元素构成的所有行，因为你都可以通过对角线取反得到一个与前面所有行不同的行。
但我们要建立一个由那些元素组成的包含所有不同行的阵列是非常容易办到的，只要不限定高必须与宽相等就行为什么在无穷领域，我们的康托尔大师既要假定阵列包含所有的行，同时又要规定阵列的宽和高必须严格相等呢？要知道，这后一个规定本身就使得前一个假设不可能成立啊！第六，他假定那个小数阵列的宽和高完全相等，实际上是运用了他自己的无穷集合元素一一对应的理论，而一一对应理论之所以有效，取决于对角线证明的结论，也就是说，他使用的是循环证法第七，无穷大无形状定理：无穷大没有确定的形状证明，用反证法，我们假定哲学上的宇宙空间是无穷大，也就是说没有比它更大的空间，显然，我们这个假设没有任何问题那么这个无穷大的形状是什么呢？若是方体，我们取其对角线作为新的边，构造另一个方体，比原方体大，与假设矛盾同样，若是设那个无穷大是球体，以球的直径为边长构建另一方体，又比原球体大，矛盾所以说，无穷大无形状康托尔对角线法的根本错误在于：他那个实数阵列，宽即实数的位数是无限的，高即实数的个数也是无限的，他假定这两个无限构成了一个正方形的形状，因之才有了对角线，这个假定违背了无穷大没有确定的形状，从而也是错误的请注意，我这里只是否定他的对角线法，并不意味着否定实数是比自然数更大级别的无穷大。
康托尔对角线法还有另一种表述方式，即所谓排中律方式，其本质与上述对角线方式是一样的著名数学家布劳威尔认为，在无穷领域，应该从根本上禁用排中律[11]也就是说，他认为排中律在无穷领域是不成立的笔者上述第二条从否定∞+1 > ∞着手否定康托尔的对角线，以及第七条的无穷大无形状定理，从实质上与布劳威尔认为排中律不适用无穷大领域的观点是一致的还有一种方式是通过改变概念和范畴来得出与康托尔相反的结论，从而否定他的理论这样的方式争议很大，并没有得到公认哲学家维特根斯坦从哲学的范畴质疑康托尔的对角线[9]本文的方法与这些有着本质的不同本文是在传统数学和逻辑观念的范畴内来论及康托尔的对角线法的 3 图灵关于停机问题的对角线证法如前所述，图灵停机问题是指：存在不存在一个程序比如说P，能够判断出任意一个程序X是否会在输入数据Y的情况下停机？我们不妨设P(X,Y)表示P判断程序是X，数据是Y的结果如果停机，那么P(X,Y)就输出一个yes如果不停机，那么P(X,Y)就输出一个no,这就是图灵停机问题. 问这样的程序P存在吗? 图灵证明,这样的程序P是不存在的,他。