计算的极限（四）~(七) [转]

有限的障壁
无限扩充得到的公理系统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）

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

从点集开始

本帖隐藏的内容

为了超越哥德尔不完备性定理，为了获得一个既不自相矛盾又能证明其中一切真理的数学系统，图灵需要从皮亚诺公理开始，一次又一次地添加新的公理，得到越来越大的数学系统。但无论添加多少次，在获得的系统中，一致性与完备性仍然不可两立，即使添加无穷条公理，也无法跨越“有限”所设置的障壁。要达到原本的目的，图灵必须尝试添加更多的公理。但既然已经添加了无限条新公理，新的公理还会起作用吗？又要怎么去描述“无穷之后”的新公理？“无穷之后”又是什么？
无独有偶，在大约五十年前的十九世纪80年代，另一位数学家也碰到了类似的问题，而他的工作正好给图灵提供了描述“无穷之后”的语言。
这位数学家叫格奥尔格•康托尔，集合论之父。

年青的康托尔，来自Wikipedia
虽然康托尔最大的贡献是为集合论奠基，但他科研生涯的起点与集合论相去甚远。他师从库默尔和魏尔斯特拉斯，博士论文的题目自然也是与数论相关。让他转向集合论研究的关键人物，是爱德华•海涅（Eduard Heine），一位专攻数学分析的数学家。康托尔博士毕业后不久，就在德国的哈雷大学找到了一份教职，而他的新同事中就有海涅。正是海涅鼓励康托尔研究有关三角级数的问题，他对康托尔提出了这样一个问题：什么样的函数拥有唯一的三角级数表达？
三角级数，顾名思义，是由正弦和余弦这些三角函数组成的级数。无论是正弦还是余弦，它们的图像都如同周期性的波纹，而实际上它们也的确描绘了各种各样的简谐振动。在数学上而言，它们是一些特别简单的周期函数，有着特别美妙的特性。但现实往往是复杂的，在工程中，为了实际应用，我们常常逼切地需要计算与工程中出现的函数有关的各种数量和性质。但这些来源于现实的一般函数，几乎不存在任何规律，同样缺乏任何可资利用的特性。于是，如何借助简单而规则的三角函数，来表达复杂而无序的一般函数，这自然同时吸引了数学家、物理学家与工程师。

三角级数正滥觞于此。在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-机”，而它的现代术语叫“谕示机”。一台谕示机就是一台有点特别的图灵机，仅仅多了一个新功能，就是能“免费”得到某一个特定的判定问题的答复。比如说，一个带有素数判定谕示的谕示机，除了能做普通图灵机能做的一切事情以外，还能瞬间判定纸带上写的某个自然数是否素数，而不需要实际去计算。
那么，是不是谕示机就一定比普通的图灵机强大呢？就像两位学生参加同一场范围不定的不限时开卷考试，他们的能力与掌握的知识相同，一位学生带了一本参考书，而另一位则什么资料都没带，带了书的那位是不是一定比另一位更有优势呢？
  
这就要看参考书到底是什么了。如果两位学生都懂参考书中的所有内容的话，那么参考书并不会带来什么优势，可能带书的学生会答得快一些，但既然考试不限时，没带书的学生多用点时间也总能答出来。但如果参考书是两位学生都没有见过的内容的话，带了书的学生自然略有优势。如果考试题目中包含了参考书中的一些内容，而两位学生本来都不懂的话，带了书的可以翻书回答，没带书的就只能干瞪眼了。