不可计算数——数学中的幽灵，揭示了一个深层次的数学哲学问题

　　
我们都知道，圆周率是无限不循环小数（3.14159265359……）。通过测量多边形的边长，我们可以把圆周率近似到想要的精度。当多边形的边数趋于无穷，边的长度趋于零时，近似值就会更接近。

• 用五边形、六边形和八边形来近似圆周率的上界和下界。

　　阿基米德（约287- 212）发明了这种早期的“多边形算法”，作为计算圆周率的最有效的方法，它统治了1000多年，可以达到任何期望的精度。这个非常原始的几何算法函数用于估算实数π，由于π不能表示为有理数，因此必须取一个近似值。

　　现代对可计算性的研究始于1900年左右，当时希尔伯特提出了“希尔伯特计划”，以公理化数学的基础。在此之前，希尔伯特本人在1899年曾表示，几何的一致性变成实数的一致性，而实数一致性又变成戴德金的算术结果。因此，希尔伯特计划是为了类似地利用数学证明的有限性来证明不会产生矛盾。如果这样的基础能够建立起来，数学证明就完全可以用逻辑符号来表达。如果实现了，所有的证明，包括费马大定理、黎曼假说和庞加莱猜想，都将是它们所表达的数学系统的必然结果。如果这是真的，我们就能造出一台足够强大的机器，让它运行足够长的时间，最终所有的数学真理都会被揭示出来。

　　不到30年后，奥地利逻辑学家库尔特哥德尔（1906-1978）发表了一篇著名的论文——《论数学原理及有关系统的形式不可判定命题》，其中他的“定理6”粉碎了希尔伯特公理化数学基础的梦想。哥德尔的研究表明，这样一个系统（无论多么强大），从本质上来说总是不完整的。在这个系统中，总有一些表述是根据公理而无法证明的：

第一不完全性定理（哥德尔, 1931a）

任何可以进行一定数量初等运算的一知形式系统F都是不完整的；也就是说，有些F语言的表述在F中既不能被证明也不能被证伪。

　　这篇论文有效地结束了希尔伯特计划。当哥德尔上台展示他的成果时（那时仅25岁），约翰·冯·诺伊曼（1903-1957）恰巧作为希尔伯特项目的代表在观众席上。冯·诺伊曼被一些人认为是有史以来最聪明的人，他立即意识到希尔伯特计划结束了。

　　冯·诺伊曼花了几周的时间准备一个相关定理的证明，该证明基于哥德尔不完备性证明的算术运算，证明“形式系统”不仅不能证明其中的每一个陈述，而且也不能保证证明其自身的一致性。后来他向哥德尔提交了证明，据说哥德尔礼貌地表示感谢，并告诉他，几周前他自己（哥德尔）也写过同样的证明，而且已经提交发表了。这个定理是：

第二不完全性定理（哥德尔, 1931b）

没有一个包含皮亚诺算术的一致公理系统能证明其自身的一致性。

　　更通俗地说，任何能够形成自身一致性的正式系统，只有当且仅当它不一致时才能证明这一点。该定理证明了第二个希尔伯特计划的内在谬误，该计划于1918年启动，名为判定问题，是否有可能提供一个判定程序，允许一个人决定一个句子的有效性。

　　因此，20世纪30年代的数学家们再次面临数学缺陷的实际含义，19世纪80年代，康托尔首次证明了这一点。

　　我们的故事从这里开始。

　　定义

　　阿基米德常数（π）、毕达哥拉斯常数（√2）和黄金比例（φ）等众所周知的数都是可以计算的实数，尽管它们也是无理数。这些可计算数可以定义为：

可以通过有限终止算法计算到任何所需精度的实数。

　　换句话说，我们判断一个实数为可计算的方法：如果有一种算法，给定n，返回该数字的前n位。非正式地说，我们可以把一个可计算的数想象成马文·明斯基所做的那样，即有一个图灵机，在初始磁带上给定n，以该数字（编码在磁带上）的第n位结束。

　　从形式上来说，实数a是可计算的，如果它可以用从自然数N到实数Z的某个可计算函数来近似，给定任意正整数N，该函数产生整数f(n)，从而：

• 给定的正整数n, f（n），可计算实数a的现代定义

　　可计算数的一个等价定义是存在这样一个函数，给定任意正有理误差界ε，得到一个有理数r，使其绝对值|r - a|小于或等于误差界ε。

　　正如康托在19世纪研究对角线论证所产生的不可数集一样，普林斯顿大学的研究人员在20世纪30年代研究不可计算数的含义。历史特别突出了阿隆佐·邱奇（Alonzo Church）和艾伦·图灵（Alan Turing）这两个人的贡献。

　　阿隆佐·邱奇

　　阿隆佐·邱奇是一位美国数学家和逻辑学家，20世纪20年代在普林斯顿大学的奥斯瓦尔德·维布伦手下获得博士学位。他发表的第一篇论文是关于洛伦兹变换的。他最著名的成果包括证明希尔伯特的判定（决策）问题是不可判定的（被称为邱奇定理），皮亚诺算术是不可判定的，他发明了λ演算，并阐明了后来被称为邱奇-图灵论题的关于可计算函数本质的论文。

　　艾伦·图灵

　　艾伦·图灵是一位英国数学家，他因协助军方破解德国的著名密码系统Enigma而闻名。对于数学家来说，图灵的名字是天才的同义词，不仅是因为他在应用理论方面的工作，还因为他在纯数学和逻辑方面杰出的贡献。

• 艾伦·图灵和《论可计算数，及其在判定问题中的应用》，载于1936年《伦敦数学学会学报》

　　图灵于1912年出生在伦敦，但在他17岁的时候就去了剑桥大学国王学院学习数学。1934年，他以优异的成绩毕业，同年被选为国王学院的研究员（仅仅因为他的论文证明了中心极限定理）。1936年，他发表了他的著名论文《论可计算数，及其在判定问题中的应用》。它分两部分发表在1936年11月30日和12月23日的《伦敦数学学会学报》上。同年9月，图灵前往普林斯顿大学，在邱奇手下攻读数学博士学位。他于1938年获得博士学位。他的论文名为《基于序数的逻辑系统》，引入了序数逻辑和相对计算的概念——用所谓的甲骨文机器来扩充他之前设计的图灵机，从而研究图灵机无法解决的问题。尽管冯·诺伊曼博士想让图灵在获得博士学位后担任博士后研究助理，但图灵拒绝了，回到了英国。

　　不可计算性

　　在1931年，将逻辑应用于可计算性是年轻人的游戏。哥德尔（生于1906年），25岁时证明了形式系统的不完备性。邱奇在33岁时，基于λ演算，发明了“有效可计算性”的概念，证明了判定问题的不可判定性。图灵，独立地证明了同样的结果，同年他发明了图灵机，当时年仅24岁。

　　判定问题

　　“判定问题”的概念，即寻找一种算法，能够根据有限的公理集确定输入的真伪的问题，可以追溯到17世纪，当时莱布尼茨首次提出了这个概念。后来，对于各种形式系统，这个问题也分别由施罗德（1895年）、洛文海姆（1915年）和希尔伯特（1918年）提出，直到希尔伯特和阿克曼（1928年）在《数学逻辑原理》（Grundzuge der theorem Logik）上共同发表了正式声明：

当我们知道一个过程允许任何给定的逻辑表达式通过有限次运算来决定其有效性时，判定问题就解决了。

　　邱奇的解决方案

　　1933年，图灵的论文导师阿隆佐·邱奇开始研究这个问题。1934年3月左右，他向哥德尔提出了他的解决方案，其中包括他所谓的有效可计算函数。据推测，哥德尔否定了邱奇的方法。基于λ演算，邱奇的第一个命题是：

可计算性的第一个定义（1934）

一个函数是有效可计算的当且仅当它是λ可定义的。

　　自1931年起，邱奇就致力于将函数定义为λ可定义函数。到1934年，他们已经证明了所有一般数论函数都是λ可定义的。然而，哥德尔在1931年的论文中所述的原始递归函数并没有包括所有可计算的函数，因此对于断言所有数的有效可计算性来说，这是一个不充分的。为了说明这一点，1934年春，哥德尔扩展了杰出的赫尔不兰特（1908-1931）定理，定义了赫尔不兰特-哥德尔递归函数。在参加了哥德尔举办的关于这个主题的讲座后，邱奇和克林最终修改了他们对可计算性的定义，改为基于赫尔不兰特-哥德尔的递归函数：

可计算性的第二个定义（邱奇, 1936）

当且仅当正整数上的函数是递归的时，它是有效可计算的。

　　邱奇和克林后来证明，他们在第一个定义中使用的λ可定义函数和他们在第二个定义中使用的赫尔不兰特-哥德尔递归函数在形式上是等价的。

　　图灵的解决方案

　　与此同时，艾伦·图灵来到普林斯顿，试图解决希尔伯特的判定问题，并在此过程中提供了可计算性的完整和最终定义。1936年11月30日，图灵在《伦敦数学学会学报》上发表的论文将可计算性定义为：

图灵的可计算性定义

一个函数是直观可计算的（有效可计算），当且仅当它可以被图灵机计算，也就是图灵定义的自动机器。

　　图灵在他的论文中指出了他的定义与邱奇七个月前发表的论文的相似之处，他说：“在最近的一篇论文中，邱奇引入了一个“有效可计算性”的概念，它等价于我的“可计算性”，但定义非常不同。他还补充说：“丘奇在判定问题上得出了类似的结论。”

　　与邱奇和克林不同，图灵的定义并不依赖于赫尔不兰特-哥德尔的递归函数。相反，图灵研究了人类是如何进行计算分析的，最终表明，同样的程序也可以由机器来执行。图灵的分析不仅仅是提供了一个论证，它证明了一个定理。图灵机的出现是他对人类计算分析的结果，是一种编码。

　　图灵机可以非正式地定义为：

图灵机（A -machine）是一种计算的数学模型，它定义了一种抽象机器，它根据一个规则表来操作纸带上的符号。尽管模型很简单，但是给定任何计算机算法，都可以构造一个能够模拟该算法逻辑的图灵机。

　　不可计算数

　　虽然我们知道实数的集合是不可数的，但可计算数的集合是可数的，因此我们知道大多数实数是不可计算的。证明可计算数是可数的，直觉上源于这样一个事实，即它们都可能是由图灵机产生的。

可计算数的可数性的证明

通过分配哥德尔数给每个图灵机定义产生一个与可计算数相对应的自然集。从S到可计算数的一个满射表明，可计算数是可数的。

数子

　　例A：蔡廷常数Ω

　　1975年，阿根廷裔美国数学家格里高利·蔡廷将一个不可计算的实数按比例分解，现在称为蔡廷常数Ω。它表示随机构造的程序终止的概率：

蔡廷的思想实验：

假设我们在一个随机二进制程序上运行一个通用图灵机。具体地说，每当需要程序的下一个比特时，我们抛硬币并将“二进制输出”输入到机器。图灵机停止的概率是多少？

　　蔡廷的思想实验是一个典型的终止问题的例子。终止问题是指从一个任意计算机程序的描述和一个输入来确定程序是结束运行还是永远继续运行的问题。图灵机U的终止概率 Ωᵤ 取如下表达式：

• 在输入σ的条件下，图灵机U的终止概率

　　其中σ代表随机有限二进制程序，U(σ)↓表示U将在输入σ时停止。

　　图灵1936年的论文证明了，对于所有可能的程序输入对，解决中断问题的一般算法是不存在的。中断的概率是无法计算的。这一事实的证明依赖于一种算法，给定前n位Ω，它解决了长度为n的程序的图灵中断问题。因为中断问题是不可判定的，所以Ω无法计算。

　　例子B：忙碌的海狸问题BB（n）

　　蒂博尔·拉多在1962年一篇名为《论不可计算函数》的论文中提出了以下问题：

给定一定数量的规则，在图灵机停止运行之前，它能执行的最大步骤是多少？

　　这个问题有一个数学函数BB(n)，其中n代表规则数，BB(n)代表这种机器可以执行的最大步数（BB(1） = 1）。对于BB（4），问题就变得非常困难。证明BB（4）是一篇博士论文。BB（5）的值没人知道，但至少为4098。BB(6)至少为3.5 x 10¹⁸²⁶⁷ 。如果运行 BB（27） 步还没停机，就说明哥德巴赫猜想成立！

　　BB（n）函数是一个不可计算函数的例子。也就是说，没有图灵机Mᴮᴮ来计算BB函数。这可以用反证法证明，这里就 不展开了。

　　例C：彭罗斯拼图

　　彭罗斯拼图是由一组非周期的原始“瓷砖”产生的非周期瓷砖的一个例子。因为这些图案是非周期性的，它们缺乏平移对称性。它们也是自相似的（分形），因为它们在越来越大的尺度上呈现相同的图案。

• 彭罗斯拼图

　　一套瓷砖是否会覆盖平面的问题是1961年王皓提出的。这个问题后来被证明是不可计算的。这个证明依赖于使用图灵机模拟图灵机，配置图灵机的方式是，只有当图灵机从一个空白磁带开始永远地运行时，它们才能覆盖整个平面。既然停止问题是不可判定的，那么平铺问题也一定是不可判定的，因此也不可计算。

　　后记

　　今天，在数学和计算机科学中，图灵机是定义可计算函数的主要形式。然而，为了承认邱奇首先掌握了这些函数的本质，关于可计算函数本质的假设的现代公式现在被称为邱奇-图灵命题：

邱奇-图灵命题

一个函数是可计算的，当且仅当它是可计算的图灵机，或等价地，如果它是指定的递归函数

　　它的含义是：

没有一种机械过程的计算方法能比图灵机更强大。

　　尽管这个命题被广泛采用，但由于没有明确的方法来证明或反驳它的有效性，它仍然是一个猜想。