哥德尔的不完备性定理有两条。

但要用这种方法在系统内部证明自身的一致性，实际上并不可行。的确，我们可以多次重复添加公理的过程，得到从T_1、T_2开始的一系列理论系统，但它们的一致性是相同的，都依赖于起始的数学系统T，而且这一点是可以证明的。既然在起始的系统中不能证明自身的一致性，那么之后的一系列系统，无论重复多少次，都不可能证明自身的一致性。
那么，如果我们重复无限次，添加无限条公理呢？这样的话，无论使用了多少条公理，总有比它们更大的一条公理将会断言前面公理的一致性，一环扣一环，直至无穷，整个系统岂不是无懈可击？
系统的证明
从某个理论T 0 =T  开始，逐次添加关于新理论一致性的公理Cons(T i )  ，不断得到T 1 =T 0 +Cons(T 0 ),T 2 =T 1 +Cons(T 1 ),T 3 ,…  ，一直到最后包含无穷条公理的T ∞   ，其中每一条公理都有更大的公理来断言它的一致性。似乎我们就得到了一个超越哥德尔不完备性定理的数学系统。
但事情当然不会那么顺利。
首先，在包含无穷条公理的数学系统中，如何在系统内部谈论它的一致性，这并非顺理成章。的确，从理论上来说，包含任意的无穷条公理的数学系统是存在的。但如果要在这种系统内思考，很快就会遇到困境。先不说在系统中进行推理，就算是阅读一个证明，也并非显然。要理解这一点，需要对“形式证明”有更具体的理解。

一个数学系统内的形式证明，实际上是一串有限的命题组合，其中的命题要么是系统内的公理，要么是此前命题明白无误的简单逻辑推论，而最后出现的命题就是这个形式证明要得出的结论，也就是要证明的定理。这种一环套一环的组合方式，恰好保证了最后结论的正确性。而我们在阅读一个形式证明时，也只需要顺次检查这些命题，看看每一个命题是否本身就是公理或者此前命题的推论，就能验证这个证明的正确性。
而如果要在系统内部用命题表达系统本身的一致性，就要用到哥德尔在证明他的不完备性定理时用到的技术。简单来说，我们需要“阅读证明”的这个过程能够完全机械化，即使将人脑换成图灵机，也可以完成类似的验证。但如果数学系统本身包含无穷条公理的话，这个机械的阅读过程可能甚至连第一步都无法开始：如果有无穷条公理，那么面对一个命题，又如何知道它是否一个公理呢？
打个比方，数学系统好比是座仓库，里边装的都是公理。现在有人给我们一件东西，比如说一本书，我们的任务则是查看仓库里是否有一模一样的存货。如果仓库里只有有限样东西，一个个清点总能完成任务；但如果仓库容纳了无数物件，即使仓库的确有相应的存货，如果清点的次序不当，也有可能永远也碰不上我们的目标。

同样，要判断某个命题是否给定的数学系统中的公理，如果公理只有有限条，那么一个一个比较，总能在有限时间内判断出来。但对于无穷条公理的情况，这种方法有着严重的缺陷。如果检查的命题的确是公理，那么有朝一日总会停止；但反过来，如果我们检查了很久，仍然没有找到它是公理的证据的话，因为我们没有清点公理的一般方法，所以同样无法断言是否有遗漏。
所以一般而言，在一个包含无穷条公理的数学系统中，我们甚至无法在有限时间内机械地判断一个证明是否正确。尽管形式上仍然可以对形式证明进行定义，但我们几乎无法有效地考察这样的定义。同样，在这类系统中，有关形式证明的概念，尤其是系统本身的一致性，也如同处于矛盾中的说谎者，根本无法被表达。在这些系统中，难以谈及有关证明论的问题。

然而，在数学家们平常使用的数学系统中，不乏包含无穷条公理的例子。其中包括策梅洛-弗兰克公理系统，它被认为是现代数学的公认基础；还有皮亚诺算术的一阶逻辑版本，这个版本在数理逻辑的研究中经常出现。虽然这些系统同样包含无穷条公理，但数学家们在使用这些系统进行证明时没有一丝的踌躇，似乎其中形式证明的意义理所当然，与我们之前的结论背道而驰，这又是为什么呢？
答案很简单：这些数学系统拥有特殊的性质，虽然包括无穷条公理，却能在有限的时间内判断某个命题是否其中的公理。在数理逻辑中，这些系统被称为可有效生成的公理系统。
“可有效生成的公理系统”，顾名思义，这种系统里的公理都是可以“有效生成”的，也就是说，存在一台图灵机，可以“生成”所有的公理，将它们一一打印到纸带上，而打印出来的命题则必定是系统中的公理。可以说，这样的公理系统可以约化为一台图灵机。
回到仓库的比喻的话，一个可有效生成的数学系统同样是公理的仓库，但其中有着某种规律。比如一个包揽全世界所有书的仓库（它的别名叫图书馆），要判断某样物品是否有存货就太简单了：只要是书，那就有存货；如果不是书，那就没有。无需费力找到具体的对应，但同样可以确定仓库中是否存在相同的存货。

如果一个数学系统是可有效生成的，那么可以构造一个图灵机来判断某个证明是否正确。它能仅仅承认那些系统内正确的证明，对于错误的证明则一律拒绝。那么，即使有无穷条公理，我们仍然能通过这台图灵机考察关于形式证明的性质，从而可以谈论所有有关证明论的问题，包括我们关心的系统一致性。
而我们希望讨论的扩充系统，也就是通过无穷次扩充得到的数学系统，的确是一个可有效生成的系统。所以，我们对它一致性的讨论是有意义的。
对于读者来说，可能会感觉这些围绕着无穷条公理的讨论仅仅是一种吹毛求疵。但对于数学，特别是数理逻辑而言，精确性无比重要。在日常生活中，我们使用的语言太模糊太杂乱，人们的本意常常迷失在语言当中，有时连人本身都不理解口中的言说。但在数理逻辑中，一切含糊都被符号明晰，没有歧义，没有矛盾，对就是对，错就是错。这种确定性，正是数学真理性的所在。

有限的障壁
无限扩充得到的公理系统T ∞   ，虽然能在其中表达系统本身的一致性，但它的一致性却不像我们想象中的那么显然。虽然对于其中的每一条新公理Cons(T k )  ，都有比它更强大的另一条公理Cons(T k+1 )  保证它的一致性，但这真的能证明包含无数条新公理的系统是一致无矛盾的吗？
我们重温一下一致性的定义：一个公理系统是一致无矛盾的，当且仅当系统中不存在对于假命题的证明。也就是说，无论系统有多大有多复杂，只要系统本身不能证明任意一个假命题，比如说“1=2”，那么这个系统就是一致的。
我们现在尝试考虑无限扩充得到的公理系统T ∞   。要超越哥德尔不完备性定理，就需要在系统内部证明有关系统本身一致性的命题Cons(T ∞ )  。假设系统中存在一个这样的形式证明P  ，这意味着什么呢？
我们知道，形式证明的长度是有限的，毕竟无论是人类还是计算机，都无法完整阅读无限长的证明。所以，证明P  用到的公理也只有有限条。既然有限，那么其中形如Cons(T k )  的公理也有限，对应的k  必然有一个最大值，不妨设为N  。那么，证明P  中的所有公理，在更小的系统T N+1   中早已存在，所以证明P  在T N+1   中同样有效。也就是说，仅仅在T N+1   中就可以证明T ∞   的一致性，它也蕴含了更小的系统T N+1   的一致性。
也就是说，因为形式证明的长度是有限的，如果无限扩充后的系统T ∞   能超越不完备性定理，证明它自身的一致性，那么在之前有限次扩充中，必然已经存在一个系统，它能证明自身的一致性。根据之前的论述，这也表示一开始的出发点——也就是系统T  ——也能证明自身的一致性，而这是不可能的。
尽管我们尝试用无限来突破不完备性定理，但名为“有限”的障壁挡住了我们的去路。

（图片来自http://www.personal.psu.edu/afr3/blogs/SIOW/）
在某种意义上，我们能够处理的，只有“有限”，而无法处理真正的“无限”。那些我们看似能抓住的“无限”，实际上也只是通过某种“有限”的手段确立的。而在“无限”的海洋中，我们无法辨别的，远多于我们能认识到的。
我们无法认识一切，相对地，我们永远有着等待探索的世界。
既然从一致性的方向无法突破，那么从另一个方向呢？哥德尔不完备性定理断言，对于合适的数学系统而言，一致性与完备性是两立的，那么，是否可以不停地扩充系统，在保证一致性的前提下，使它能证明越来越多的命题呢？最后又是否能得到一个完备的系统，在其中可以证明所有真命题呢？
为了回答这个问题，图灵将眼光投向了无穷的彼岸。
（如非特别说明，插图由Neko提供，微博号@NEKOinHeaven）

计算的极限（六）：无穷的彼岸

从点集开始

三角级数正滥觞于此。在1822年，法国数学家傅里叶在他的著作《热的解析理论》中，为了研究热传导的现象，将热量的分布函数分解为三角函数的级数和，并且提出一个构想：所有函数都能表达为三角级数。
当然，事情并没有那么简单。尽管现实中遇到的函数（连续函数）都拥有这样的表达，但对于更为复杂的函数，这却不一定成立。另外一个问题是，对于任意的一个函数，尽管都可以通过傅里叶变换得到对应的三角级数，但谁也不知道会不会有另外一个三角级数也会给出同样的函数。也就是说，虽然通过傅里叶变换，可以知道必定存在一般函数的三角级数表达，但这种表达是否唯一，却并非显然。
康托尔一开始希望解决的，就是这个问题。
凡事总得一步一步来。在1870年，康托尔证明了某个区间上的连续函数必定有唯一的三角级数表达，后来又证明了，即使函数在区间中的有限个点处不连续，也不影响这种表达的唯一性。最后，他在1872年证明了一个非常广泛而复杂的结论：如果函数在区间上大体是连续的，只有在某个点集P上的点不连续，那么如果P满足某个复杂的性质，那么函数就有唯一的三角级数表达。

线性函数的傅里叶级数展开，来自Wikipedia
而正是这个“复杂的性质”，向康托尔暗示了无穷之外另有洞天。
对于任意的点集P，我们可以构造另一个点集P'，它包含所有可以用P中的点无限逼近的点。用数学的术语来说，点集P中的某一点p在P'中，当且仅当对于任意小的距离e，都存在P中不同于p但与p距离小于e的点。既然e可以要多小有多小，这也就是说可以用P中的其他点无穷逼近我们所考虑的点p。这样构造出来的点集P'，又叫P的导集。导集P'本身也是点集，所以它同样有自己的导集，记作P''。导集的导集也有自己的导集，如此反复，直至无穷。我们可以将P取n次导集操作后的结果记为P (n)   。
容易知道，一个点集的导集必定是点集的一个子集。实际上，从不太严谨的观点来看，求导集这一操作可以看作一个将点集中那些“离散”的点，也就是那些与所有其他点“保持某个距离”的孤零零的点（或者叫孤立点），从点集中去掉的操作。在一次又一次求导集的操作中，由于我们不停地去掉孤立点，可能会有新的点因为我们除去了它的所有“邻居”而变为新的孤立点，所以多次求导集并非没有意义。

数量与顺序

对于有限个物品来说，如果不考虑物品之间的差异的话，清点的方法只有一种。无论是红蓝绿还是绿红蓝，实际上都是1-2-3这个清点顺序。所以对于有限而言，数量和顺序之间可以一一对应起来，所以我们只需要自然数这一个概念，就能同时描述有限的数量与有限的顺序，每一个自然数也因此具有双重的含义。但对于无限个物品来说，即使是同一堆东西，我们也可以有无穷无尽的清点方法。我们最常接触的有无限个元素的集合，就是所有自然数组成的集合，这个集合就可以有许多种不同的清点方法。
最自然的方法当然是从小数到大：
0, 1, 2, 3, 4, ...
也可以先数偶数，再数奇数：
0, 2, 4, 6, ..., 1, 3, 5, 7, ...
也可以先数质数，再数合数，最后数1：
2, 3, 5, 7, 11, ..., 4, 6, 8, 9, 10, ..., 1
当然也可以先数比5大的所有数，然后再数剩下的：
6, 7, 8, ..., 0, 1, 2, 3, 4, 5
清点的方法无穷无尽，但自然数的个数应该是一个固定的量，独立于这些各不相同的清点方法。康托尔洞察到了这一点，他意识到，对于无穷而言，需要用两个不同的概念，分别描述数量与顺序。为此，他提出了基数与序数两个概念，前者描述集合的数量，后者描述清点的顺序。这两个概念一直沿用至今。给出一个清点的顺序，自然能得到集合中元素的数量，所以一个序数对应着唯一的基数；但对于某个特定的集合，它可以有许多种不同的清点方法，所以一个基数可以对应许许多多不同的序数。对于有限的集合来说，它们的基数对应着唯一的序数，所以可以将二者混为一谈，这正是我们常用的自然数。
在厘清有关无限的观念滞后，关于点集导集的谜题就自然消解了：当我们说“进行了无限次导集操作之后再取导集，也是相当于取了无限次导集时”，实际上我们谈论的是操作的数量；但导集毕竟是一个操作，逐次重复操作的结果有着内在的顺序关系，先有前面的结果，再有后面的结果。导集的结果，实际上对应的是序数，而我们却用基数的观念来思考，当然会导致似是而非的结果。
实际上，许多关于无穷的看似矛盾结论，都可以归根于我们在日常经验中对数量与顺序的混淆。比如说有人会认为偶数比自然数少，是因为自然数除了偶数之外还有奇数，但实际上这种说法隐含了“先数偶数再数奇数”的这一清点顺序，用这种方法偶数会比自然数先清点完，而我们现在知道，对于无限个物品来说，可以有无数种不同的清点方法，清点方法一先一后穷尽，并不必然代表数量一大一小，关于无穷的怪论也就自然消解了。我们在日常生活中接触到的物体都只有有限个，所以将基数和序数混为一谈也没有关系，但对于导集这种可以产生无穷个对象的机制来说，基数与序数，也就是数量与顺序，一定不能混淆。

以此为基础，康托尔意识到了集合的重要性，并以此为基础发展出了朴素集合论，也意识到“无穷”也有无穷个不同的级别，并称之为“超穷”，意即超验（超越日常经验）的无穷。经过第三次数学危机之后，由朴素集合论发展而来的公理集合论已经成为公认的数学基础。对公理集合论的研究，已经成为了数理逻辑的重要研究方向之一。而超穷基数与序数也已经成为数学研究中不可或缺的概念。希尔伯特这位大数学家的评价或许最为恰当：“没有人能将我们驱逐出康托尔创造的这片乐园”。

序数构成的螺旋，图片来自Wikipedia
但康托尔本人的命运却远不如他的理论那么幸运。他提出的基数与序数，一开始并没有得到理解，也因为涉及到无穷，以及无穷种无穷，而被当时执德国数学界牛耳的数学家克罗内克所排挤与敌视。克罗内克的格言是“上帝创造了自然数，其余一切均是人为”。他连超越数也不承认，康托尔提出的“超越经验的无穷”，也就是拥有无穷个阶别的无穷，对于这位“统治”当年德国数学界的数学家来说自然是“大逆不道”，甚至到了多次在公开场合言语攻击康托尔的程度。再加上康托尔的理论本来就难以为当时的数学家所理解，因此康托尔在当时的数学界过得并不特别好，一直郁郁不得志，这种压力可能也是他患上精神分裂症的诱因之一。康托尔那辗转于疗养所的晚年，也许部分而间接地要归根于他那伟大的洞察。
生命是灰色的，而理论之树常青。

无穷的彼岸
但对于五十年后的数学界来说，基数和序数的概念早已被广泛接受，图灵对此自然也非常熟悉。利用序数的概念，来探寻无穷扩充之后的公理体系，亦是水到渠成之事。窥探无穷的彼岸，不再是一件不可思议又充满矛盾的事，而是确确实实令人信服的数学手段。
对一个公理系统进行扩充，可以看成对公理系统的一种操作，正如取导集可以看成对点集的一种操作。对于无限次操作之后得到的结果，再施加一次操作，也是有意义的。对于操作来说，重要的不是数量，而是操作的顺序，而序数正适合标记这种顺序。
利用序数，我们能表达无穷次扩充后得到的公理体系。就算无穷次扩充之后，我们仍能一次又一次地进行扩充，直到无穷；但仍能继续扩充，直到无穷次无穷，无穷次无穷次无穷，无穷次无穷次无穷次无穷，如此等等，不一而足；但这并不是终点，我们甚至还能继续进行体系的扩充，达到连用“无穷次无穷次……无穷”也需要重复无穷遍的地方……这令人头晕目眩，但序数可以轻易表达这一切，而这只是序数涵盖领域的九牛一毛而已。
于是，我们能一刻不停地扩充原有的体系，得到一个又一个的新体系，这个过程永无止尽，每一个新的体系都比原来的更强大，而每个体系都拥有自己的一个序数，标志着它们在这个超穷的扩充过程中出现的顺序。每一个能表达出来的序数，都对应着一个公理系统。而所有这些公理体系，依由它们对应的序数，组成了一整个层次结构。

图灵将这一系列的公理系统称为序数逻辑，这个原创的体系正是他的博士论文的研究内容，而提出新研究体系的博士论文，可是凤毛麟角。

他希望这个工具能在某种意义上超越哥德尔不完备性定理。虽然任何一个（可有效生成的）公理体系都不可能同时是一致而完备的，但对于一系列的一致的公理体系而言，这种限制并不存在。即使其中每个公理体系都有不可证明的命题，但如果对于任意的命题，都能在序列中找出一个能证明或否定它的一致的公理体系，那么，在作为一个整体的意义上，这一系列的公理体系是完备的。当然，这与哥德尔不完备性定理并不矛盾，因为一系列可有效生成的公理体系，它们合并起来并不一定是可有效生成的，既然定理的前提不适用，那么定理的结论自然也不适用。
那么，在这个层次结构中的一个“证明”，应该是怎么样的呢？
因为命题总是要在某个体系中被证明，所以首先要指定一个体系，相当于指定这个体系对应的序数，剩下的就是直接写出这个命题在对应体系中的证明。当我们要检验一个证明时，首先查看指定的序数，然后查看对应的体系中的公理，知道公理之后就能如同一般的证明一样进行检验了。也就是说，跟一般的证明相比，在层次结构中的证明只是多了“指定证明所在体系的序数”这一步，似乎没什么了不得的。
但魔鬼往往潜藏于细节之中，这一步并不像想象中那么容易。
直觉与技巧
序数是超穷的，比无穷还要无穷，但证明的长度是有限的。所以，我们实际上不能任意指定序数，而只能指定那些我们用有限个符号能够表达的序数。所以，实际上我们指定系统用的不是序数，而是序数的一种表达方式。这种表达方式要满足两个条件：表达式的长度是有限的；如果某个序数能够被表达，那么小于它的所有序数也应该能被表达。当然还有一些技术上的条件，但我们暂时按下不表。
满足这两个条件的序数表达方法很多，图灵选择的是其中最复杂的一种：克林-O  表达。这种方法用自然数的因子分解来表达序数。虽然这种方法并不能表达所有序数，但在某种意义上，它已经是最强大的表达序数的方法。但与强大能力相随的是这种方法极端的复杂性。实际上，要判断某个自然数是不是一个序数的表达，这是一个高度不可计算的任务，虽然对于特定的自然数，可能可以进行判断，但不存在统一的判断程序。
既然不可计算，那么也无法验证，那么这种证明还有意义吗？

要回答这个问题，我们先回想一下：在做数学证明题的时候，我们到底在做什么？

第一步，一定是审题，弄清楚题目讲的是什么数学内容，是立体几何还是圆锥曲线，又或者是各种函数。不仅是简单的分类，有时一类问题会伪装成另一类问题，比如戴着“圆锥曲线”帽子的数列，或者披着“概率”外衣的组合。搞清楚具体的问题，搞清楚要证明的结论，这才是完整的审题。第二步，才开始正式的证明，在前一步的结果指引下，用对应领域的定理，慢慢探索从条件到结论的路径。而写在答卷上的，就是第二步得出的证明。审题虽然重要，但并不体现在证明中。
数学的可靠性，植根于证明的严谨性。但如何得到一个证明，却难以仅仅依赖严谨的逻辑。比如，命题需要用哪一个数学体系，这就难以用逻辑判断，需要数学家本人的直觉。也就是说，证明某个命题，其实需要两个部分的工作：第一部分来源于直觉，指引着证明的方向；第二部分来源于技巧，将直觉付诸实践。
作为一名数学家，图灵对数学证明中发生的一切当然深有体会。他认为，这种直觉与技巧的关系，与他的序数逻辑当中的证明不谋而合：指定序数的步骤，相当于直觉，告诉我们应该在超穷的层级结构中的哪一个数学体系中寻找证明；具体证明的步骤，相当于技巧，从直觉指定的公理出发，一步一步迈向需要的结论。而序数逻辑甚至将直觉与技巧的关系发挥到了极致：需要用到直觉的，只有开头的一步，但这一步是高度不可计算的，是逻辑不可能完成的任务；而剩下的，则是完全逻辑化的证明，甚至可以用机械完成。也就是说，可以说在序数逻辑的证明中，直觉与技巧的部分完全独立，一览无遗。
图灵认为，这正是他的序数逻辑存在的意义。
但世事往往不如人意。图灵研究的序数逻辑，主要是通过一致性断言扩充而得到的，而这种序数逻辑并没有图灵所期盼的那种完备性。图灵只能证明，他的序数逻辑对于一小类命题（所谓的Π 0 0   类）是完备的。这并不尽如人意，但至少第一次跳出了哥德尔不完备性定理的界限。
然而，以后见之明看来，图灵的博士论文中，最大的贡献并不是序数逻辑。在论文第四节中，图灵提出了一个孤立的新概念，这个概念对于论文的其他部分并无深刻贡献，图灵也未曾深入探讨，这使整个第四节看似无关紧要。但在后学看来，这个新概念却是整篇博士论文中最重要的部分，甚至比序数逻辑更重要。可以说，这个概念后来开创了可计算性理论的又一片新天地。
这个概念，叫谕示（oracle）。

计算的极限（七）：宛如神谕

图灵的哑谜
说到底，谕示是什么呢？我们来看看图灵在他的博士论文中的定义：
“假定我们拥有某种解决数论问题的未知方法；比如说某种谕示。我们不深入这个谕示的本质，除了它不可能是一台机器这一点。通过谕示的帮助，我们可以构筑一种新的机器（叫做o-机），它的基本过程之一就是解决某个给定的数论问题。”
在这里，图灵说的“数论问题”，其实是指描述自然数的一类特殊的逻辑命题，用现在的术语来说叫Π 0 1   命题。“数论问题”只是图灵取的一个名字，与真正的数论研究关系不大。
图灵的这段文字其实定义了一种新的图灵机，图灵把它叫做“o-机”，而它的现代术语叫“谕示机”。一台谕示机就是一台有点特别的图灵机，仅仅多了一个新功能，就是能“免费”得到某一个特定的判定问题的答复。比如说，一个带有素数判定谕示的谕示机，除了能做普通图灵机能做的一切事情以外，还能瞬间判定纸带上写的某个自然数是否素数，而不需要实际去计算。
那么，是不是谕示机就一定比普通的图灵机强大呢？就像两位学生参加同一场范围不定的不限时开卷考试，他们的能力与掌握的知识相同，一位学生带了一本参考书，而另一位则什么资料都没带，带了书的那位是不是一定比另一位更有优势呢？
  
这就要看参考书到底是什么了。如果两位学生都懂参考书中的所有内容的话，那么参考书并不会带来什么优势，可能带书的学生会答得快一些，但既然考试不限时，没带书的学生多用点时间也总能答出来。但如果参考书是两位学生都没有见过的内容的话，带了书的学生自然略有优势。如果考试题目中包含了参考书中的一些内容，而两位学生本来都不懂的话，带了书的可以翻书回答，没带书的就只能干瞪眼了。

同样，在我们比较一台谕示机与一般的图灵机的能力时，也要看看谕示回答的具体问题是什么。如果谕示解决的问题本来就是可计算的话，一般的图灵机即使没有谕示，也能多花点时间把答案计算出来，这时谕示机毫无优势；但如果谕示能解决一个不可计算的问题，比如说停机问题的话，谕示机显然能解决同样的问题，而一般的图灵机则无法解决，因为问题本身是不可计算的，这时谕示机的能力显然比没有谕示的图灵机要强。
所以说，谕示机的力量蕴含在它拥有的谕示能回答的问题，而谕示机中谕示的具体问题可以是任意的。我们可以考虑带有停机问题谕示的谕示机，如果这台机器的纸带上写着一台普通图灵机的“代码”以及输入，那么它不需要计算就能可以瞬间知道，这台普通图灵机遇到指示的输入时到底会不会停机。所以，对于谕示机而言，它不受普通图灵机的可计算性的限制，能够“计算”超越机械计算本身极限的问题。当然，这也意味着，对于一个不可计算的问题，我们不可能实际地建造一台谕示机。
也就是说，谕示机这个概念，只是一个单纯的数学概念，仅仅用于数学上的探索，而不可能实实在在地出现在我们面前。图灵当然也意识到这一点，在他的论文中，也确切声明谕示机并不属于机械计算的范畴。也许这就是图灵使用“谕示”这个名字的原因。“谕示”的原文oracle，来自拉丁语中的oraculum，从orare加上物化工具后缀-oculo得到。orare的意思是“祈求”或者“祷告”，而oracle的意思就是“神的宣布”，也就是神谕。图灵是一位无神论者，他相信神是不存在的，所以神谕当然也不存在。用它来命名一台不可能实现的机器，实在是再适合不过了。

那么，在论文中图灵用谕示机证明了什么呢？
图灵考虑的是一类特殊的谕示机，其中的谕示能回答一切“数论问题”，也就是说，这个谕示能判断任意的“数论问题”是否为真。但除此之外，它就是一台普通的图灵机，于是我们也能考虑关于它的停机问题：给定一台这样的谕示机的代码（不包含谕示本身），以及一个输入，这台谕示机在这个输入上会不会停机呢？
对于普通的图灵机而言，停机问题是不可判定的，这早已被证明。而图灵发现，即使将证明中的所有“图灵机”三个字都换成“带有‘数论问题’谕示的谕示机”，其他部分一字不易，证明依然成立！也就是说，就像普通图灵机不能解决关于自身的停机问题，谕示机也不能解决关于自身的停机问题，无论它的谕示有多么强大。
所以，图灵的结论是，存在带有“数论问题”谕示的谕示机也不能解决的问题，但既然这种谕示机能解决所有“数论问题”，所以不能归结为“数论问题”形式的数学问题是存在的。
这个结论，未免大材小用。不需引入谕示机，以图灵的才智，也有办法证明相同的结论。在整篇论文中，谕示机这个概念只出现在第四章，专门用于探讨“数论问题”的局限性，而这一章基本与论文全体独立，即使删去也不影响结论。用不必要的工具，证明了不必要的结论，图灵到底在想什么，其中是否别有深意？为什么要加上这一章？这些问题的答案，只有图灵自己知道。
幸而，仅仅5年后的1944年，就有人破解了谕示机的哑谜。

谕示机的谕示
让我们回到开卷考试的比喻。在日常生活中，范围不定的考试毕竟少见，多数考试的范围都是相对明确的某个科目，比如说高考语文、数学分析、考研英语、公务员考试中的申论等等。我们经常说，某某省的高考数学难度比某某省的要大，或者高等数学比数学分析要简单。那么，当我们说“某门科目的考试比另一门简单”的时候，我们到底在说什么？
我们尝试一下用数学家的思路来解决问题。
首先，我们希望比较不同的科目，给它们排个顺序。我们潜意识认为，每个科目都有它固有的难度。如果科目A比科目B要难，科目B比科目C要难，那么科目A比科目C要难。也就是说，这种顺序是有“传递性”的。于是，从数学的角度来看，我们要考察的是不同的考试之间的所谓“序关系”，也就是说它们之间两两的难度顺序关系。
其次，我们也发现并不是所有的科目都能相互比较。比如说高考理科数学和对外汉语，高三理科生对前者可能驾轻就熟，但对后者大概一筹莫展；而对外汉语专业的大学生可能恰好相反。所以，科目之间的难度不是一个绝对的数字，有些科目之间不能比较。这与日常生活中的“顺序”关系很不相同，比如说日期或者温度，总有个前后高低之分，不会有两个不能比较的日期或者温度。像日期和温度这类总能比较两个元素的序关系，在数学上被称为“全序关系”；像考试科目这类不一定能比较任意两个元素的序关系，则被称为“偏序关系”。这里的“偏”跟“以偏概全”中的意思差不多，指的是“不全面”。

现在我们知道，我们要寻找的其实是考试科目之间的偏序关系。那么，给定两个考试科目，有什么办法能分辨两者孰难孰易，又或者无法比较呢？

有一些科目之间是很容易比较的，比如说小学数学当然比中学数学要容易，这是因为中学数学包含了小学数学的内容。一名能完成中学数学考试的学生，必定能完成小学数学考试。但有一些科目就不那么好比较了。线性代数和简单电路计算，初看风马牛不相及，一个是数学一个是物理，似乎没法比较。一个会线性代数的学生，如果没学过电路，似乎也没有理由能进行电路的计算。但如果这位学生知道基尔霍夫定理的话，他就能将电路计算的问题转化为线性方程组，从而用线性代数的知识去解决电路计算的问题。从这一点上来看，似乎电路计算要比线性代数容易，因为存在一种机械而固定的方法（电路的基尔霍夫定理），将电路计算的问题转化为线性代数的问题，而线性代数的问题则不一定能表达成电路的形式来求解。
把这种直觉抽象成数学语言的话，如果对于两门科目A和B，存在一种简单的方法P，能将科目A中的任意问题转化为科目B中的问题的话，那么B就不比A更简单，因为如果我们能解决科目B中的问题，那么面对科目A中的一个问题，我们只需要先用P将这个问题转化到我们能解决的科目B中，再用我们的知识去解决转化后的问题，那么就相当于间接解决了科目A中的原问题。如果这种转化是双向的，也就是说如果存在另一种方法能将科目B中的任意问题转化为科目A中的问题，那么我们就说A与B难度相当，否则我们就说B比A难。

这种将一个领域的问题变换到另一个领域来处理的方法，在数学中被称为化归或者规约（reduction），是数学家们常用的手段。将组合计数问题化归成连续函数的计算与展开，将代数方程的解空间化归成连续流形，不同的化归手法被数学家们源源不断地创造出来，一开始是神来之笔，但经过几代数学家的努力，最后积淀下来的就是一门全新的数学分支。通过规约，数学家能借用不同领域的各种工具来解决千变万化的各种问题。可以说，对于规约这一门手段，数学家们是再熟悉不过了。但将“规约法”本身抽象出来，则需要真正的数学洞见。
也许是因为太熟悉太习以为常，几乎没有人想到，规约法暗含着计算的另一重含义。

回到考试科目的比喻。如果有两门科目A与B，它们非常非常难，没有学生能不靠课本完成考卷里的任何一道题目，但只要有相应的课本，那么要拿到满分也不是特别困难。虽然两门科目都很难，但大家一般也认为B比A要更难一些。幸而这两门考试都是开卷，所以也没有人抱怨。有一天，一位学生急匆匆跑到科目A的考场，打开书包一看，才发现课本拿错了，手上只有科目B的课本。怎么办？
一般来说，开卷考试带错课本基本上就是死路一条。但我们知道科目A比科目B要容易，也就是说，存在一种方法，可以将科目A的问题转化为科目B的问题。那么，既然有科目B的课本，那么如果这位学生同时也知道问题转化的方法，那么先将试卷上的问题转化为科目B的问题，然后参考科目B的教科书解决这些问题，根据对应问题的答案，自然就能完美完成科目A的考试。
而谕示机，实际上就是一名带着课本参加开卷考试的学生。
判定问题即是考试科目，课本即是谕示，而学生本人，则是带有程序的图灵机。而我们比较考试科目相对难度的方法，实际上就是比较判定问题相对难度的方法。
我们知道，一台谕示机其实就是一台图灵机加上一个能解决某个特定判定问题的“谕示”。假设我们有两个特定的判定问题A与B，而我们希望比较两个问题的“难度”。对于判定问题A，我们将记载了A的所有解答的谕示称为谕示A。那么，我们考虑那些带有谕示A的谕示机，它们都能很快解答A的任意实例。如果存在一台这样的谕示机，它总能正确解答判定问题B的话，那么我们就说问题A至少比问题B要难。这跟开卷考试一样，不能奢求每位学生都知道怎么将科目B的问题转化到科目A中，但只要有一名学生知道怎么做，那么这种转化的方法就存在。在这种情况下，我们说问题B能够“图灵规约”到问题A，可以记作B≤ T A  ；如果同时问题A也能图灵规约到问题B的话，我们就说A与B是“图灵等价”的。
通过图灵规约与谕示机，我们可以比较不同的判定问题之间的相对难度。但谕示机本身就是一种计算方法，它从一个已知的问题出发，通过谕示假定这个问题已经被解决，从而探索那些相对于已知问题而言可以计算的问题。带有某个特定谕示的谕示机，它们能进行的计算是相对于某一个特定问题而言的。某个问题能否计算，取决于我们手上的谕示，换句话说，我们手上已有的知识。
作为一个概念，可计算性是相对的，而不是绝对的，这就是谕示机带给我们的谕示，也许也是图灵论文中哑谜的答案。
那么，揭示出这个谕示的，到底是怎么样的人呢？

再谢谢

感谢楼主慷慨分享！

thanks for sharing

谢谢分享！