哥德尔与可计算性理论——哥德尔可以有丘奇-图灵论题吗

从概念自身的稳健性，哲学内涵的微妙性以及其广泛的应用性而言，对能行可计算性“effective calculability”这个概念的澄清可以看作是20世纪逻辑成就中最重要也最有意思的。几乎同时出现于1936年的四种不同的尝试用形式化手段去精确刻画能行可计算性的努力最终可谓殊途同归，因为从外延角度而言它们被证明是逻辑等价的。所有能行可计算函数恰好就是一般递归函数或者图灵可计算函数这个论断今天几乎被所有人接受，它就是著名的“丘奇-图灵论题”(Church-Turing Thesis，后文用CTT指代)。

然而，从认识论的角度而言，CTT的性质远不如可计算性理论这一领域的技术性成就那么明确。尤为有意思也很有启发性的一个视角便是哥德尔在可计算性理论的创立历史中所扮演的角色。尽管在可计算性理论的发展中也起过积极的作用，但哥德尔的角色始终都不是核心。令人费解的是，尽管可计算性理论的所有技术细节他都了然于胸，但是哥德尔却拒绝——或者至少说不情愿——提出一个后来以丘奇(和图灵)命名的“论题”，但是哥德尔最终又为图灵的分析所折服而愿意接受这个论题。

因此，一个很自然的问题就是：为什么在可计算性理论的诞生和发展过程中哥德尔明明可以做得更多，但是终究却只是一个旁观者?一个相关的但是更为具体的问题便是：为什么哥德尔最终又完全接受了CTT，但是只接受图灵的版本(TT)而一直拒绝丘奇的版本(CT)，尽管图灵的分析和丘奇的分析在外延上是逻辑等价的?对这些问题的探讨不仅有助于我们更好的了解可计算性理论的历史以及哥德尔的实在论，同样也能更好的审视CTT所带来的认识论挑战和意义。

直观上而言，任何一个算法或是机械程序都必须能被完整而清晰的描述。在应用这个算法解决具体的问题时无需任何创造力或是独特的发明。一般而言，我们称一个程序M是能行的如果M满足如下几个条件：

尽管这四个条件也许还不足以唯一的框定一个精确的概念，但是至少我们已经将其变得足够清晰了。

对能行计算性和机械程序的精确定义的寻求最直接的动机在于一阶逻辑的一个问题：可判定性。判定问题第一次出现在也许是现代逻辑最早的著作之中，希尔伯特将其表述如下：如果我们知道一个方法能在有穷多步之内断定任意一个逻辑表达式的有效性或是可满足性的话，那么判定问题就将迎刃而解。历史上其他数学命题的不可解通常都是相对的，比如说古希腊著名的倍立方体和化圆为方的问题，与之相对，判定问题的不可解证明则要求我们对所有能行的方法给出一个严格的数学定义。

能行可计算性这个概念显得不可或缺的语境是若干具体数学问题的解决，比如希尔伯特第十问题。很明显为了解决这个问题我们需要对所有能行方法这个整体给出一个数学上精确的定义。上述例子说明除了纯粹逻辑的考虑，很多自然的数学问题本身也需要我们有一个关于能行可计算的精确定义。

出于罗素类型论的若干不足以及为了规避不完全性定理等考虑，丘奇早在1932年就尝试过提出一个全新的作为数学基础的逻辑系统。尽管这个系统很快就被证明是不一致的，但是其中极其富有成效的一部分还是保留下来了，这就是λ-演算以及相应的λ-可定义函数。丘奇认为“能行可计算”这个概念应该等同于“λ-可定义”，并且当哥德尔于1933年秋访问普林斯顿高等研究院时丘奇向哥德尔提出了这个想法。

根据哥德尔的回答，我们最多只能说哥德尔信服的是如下论题：哥德尔论题(Gödel’s Thesis，GT):每一个能行可计算函数都可以用最广泛意义下的递归程序义。虽然并没有从哥德尔那里得到证明的支持，但是丘奇还是决定坚持自己的看法，即将λ-可定义性等价于能行可计算性，并且在1935年4月19日在纽约召开的美国数学协会的一次会议上第一次公开宣布了他的“论题”，虽然这时丘奇只提供了一个摘要。

我们可以确定的说，在1936年追寻能行可计算函数的精确定义过程中，一方面，哥德尔一点都不确信他自己所提出的一般递归函数囊括了所有可能的递归形式，另外对丘奇提出的将λ-可定义性等同于能行可计算性的方案极端不满意。另一方面，对丘奇来说，这两个定义都是同样自然的，并且数学中几乎所有已知的可计算函数都可以被它们所定义这一经验事实，以及如此不同的形式定义最终居然是逻辑等价的等等诸多证据都足以让丘奇确信能行可计算性这个非形式的概念可以被精确的界定，“丘奇论题”便从此面世。

与普林斯顿那边的氛围不同，图灵几乎是靠一人之力做出他的非凡工作的。图灵最先是在纽曼1935年的课上接触到一阶逻辑的可判定问题，然后便开始着力解决它。图灵大概于1936年4月中旬给出了一个答案，并且向纽曼提交了一篇名为“论可计算数以及在判定问题上的应用”的手稿。然而，1936年5月丘奇发表的同一主题的论文很快就传到了剑桥。虽然结论相同，但图灵的分析不同于丘奇，根本不影响其价值。因此图灵最终于1936年5月28号提交了他的文章，并在8月份加了一个附录证明他的可计算性概念和λ-可定义函数的等价性。修改后的全文发表在了1936年的《伦敦数学学会会刊》上。在丘奇很快完成的一篇评论文章中他第一次使用了“图灵机”这个概念，从此“图灵机”面世。图灵在他的文章中提出了一个类似丘奇论题的想法：一个数是在直观意义上可计算的当且仅当它是可以用图灵机计算出来的。

1936年，图灵提出了抽象的计算模型图灵机(Turing machine)

早在1935年，基于对可计算函数独立于所定义系统的“绝对性”发现，哥德尔已经认定他的定理可适用于所有的形式系统。在很多其他公开的场合，尤其是在讨论哲学问题时，哥德尔都在反复的强调图灵的分析的重要性，并且认为只有图灵的分析才完全建立了对机械程序数学定义的正确性。在一个写于1965年著名的附录中，哥德尔强调了图灵工作的重要作用，并且认为只有图灵的分析提供了关于形式系统“绝对精确且毫无疑问得充分”的定义。图灵的贡献在于他给出了关于“机械程序”(或者说“算法”“计算程序”)这个概念的分析，并且证明了它和“图灵机”等价。

值得注意的一点是，与丘奇不同，哥德尔几乎从来没有以不同定义方式的汇集或是找不出反例的经验证据来论证可计算性定义的正确性。那么除了汇集论证以及经验归纳之不足之外，还有什么理由让哥德尔只相信一个非形式的“哥德尔论题”，而不愿意接纳一个数学上更加确定的丘奇论题呢?

对丘奇而言，直观上的能行可计算性并没有一个精确的定义，需要我们来选择或是约定一个足够精确且实践上有用的定义。对哥德尔而言，看似缺乏精确的定义并不代表关于这个概念的正确且充分的分析永远不存在。一个在我们看来初始模糊的概念在正确的视角引导下可以变得精确，这种对待概念的实在论立场以及对充分的概念分析之可能这一乐观态度，在我看来，最好的解释了哥德尔对汇集论证以及经验证据的保留，对丘奇论题的不满以及他对图灵关于有穷程序的分析和相关的图灵论题的赞赏。的确，图灵所给出的结果和其他不同方式给出的结果后来被证明是等价的，但是这丝毫也无法弥补其他分析所缺乏的内在可信性。在哥德尔看来，图灵的论证是一个概念分析的典范，也是他所赞赏的公理化方法的具体运用。

除了汇集论证以及无反例的归纳证据之外，丘奇还提出了一个后来被称之为“逐步论证”(step-by-step argument)的想法。丘奇是从逻辑的角度来考虑可计算性的，将可计算性视为某种特殊的逻辑推演或证明。丘奇论证中的核心假设在于每一个原子步骤都是递归的，以此来论证所有可计算函数都是递归的，这无疑是陷入了某种微妙的循环：他无法以独立于递归的方式来规定任意一个由能行程序而产生的形式系统。丘奇认为在定义形式系统时这是不可避免的。接下来我们要看看图灵的分析是如何克服这一看似不可避免的循环的。

图灵给出了不同的论证来支持他的断言，即图灵机可以计算所有直观上可以计算的函数，也就是“图灵论题”。图灵最独特也是最有说服力的论证是他对计算的直观的概念分析。他并不是从数学或是逻辑的角度来看待计算，而且直接考虑问题的核心：真正的计算过程中到底有哪些可能的过程?在日常生活中的计算通常需要计算者用纸和笔来对某些符号(通常是数字符号)进行一些变形和操作。图灵假设代表数字的符号是有穷的，计算者在任何时刻的行为都是由他所处的某个状态以及他所观察到的符号所决定的。图灵同样假定计算者的所有行为都可以被还原为一些最为基本和原初的操作，比如说改变所观察到的方块中的符号(重写或是擦除)。图灵宣称“这些操作囊括了在计算一个数的过程中所有可能的步骤”。对符号过程以及计算步骤的强调，而不用考虑它相对于任何数学或是逻辑的形式系统的依赖性，这是图灵可计算性这个概念的一个视角转换式的分析。

更重要的是，我们还可以从公理化的角度来理解图灵的分析，从而使得“图灵论题”比“丘奇论题”更加精确和严格。假设我们用“计算者”来指代一个用纯粹机械的方式来进行计算的理想化的人。那么，依照图灵的分析我们可以得到如下三个关于“计算者”的限制性条件，或者说公理：

如果我们将满足上述公理的理想计算者所能计算的所有函数称为“计算者可计算函数”，那么图灵实际上证明了任何“计算者可计算函数”都是图灵机可计算的。于是，图灵论题就可以还原为如下“中心论题”：任何机械程序都可以通过满足上述公理的计算者实现。

由此，图灵的断言“所有能行可计算函数可以等同于图灵机可计算函数”实际上可以看成是有两部分组合起来的结论，一方面，他通过精确的概念分析将能行程序还原成了在满足一些条件限制后一个理想的计算者用若干原初的计算过程组合而成的所有过程。另一方面，他严格的证明了任何通过这些原初的计算过程组合而可以被计算的函数都可以用图灵机来计算。从这个角度我们便不难看出哥德尔对图灵的分析的赞赏。

另一方面，图灵的分析所允许的公理化处理也符合一开始丘奇所提到的“哥德尔当时的想法似乎是希望能将能行可计算性看作一个原初的概念，然后试图找出几条体现这个概念核心性质的公理，再将这个理论发展下去”。有界性、决定性和局部性可以看作是机械计算的本质属性，通过由满足规定这些属性的不同公理可以得出定理：所有“计算者可计算函数”都是图灵可计算函数。这一分析，不仅克服了丘奇的论证中的循环瑕疵，同样也将图灵的分析以及图灵论题提升至一个不容怀疑的地步。

因此，无论是从概念分析还是公理化方法的考量而言，图灵的分析都要远胜于丘奇，这大概就是哥德尔只信服图灵论题最重要的原因，这也很好的解释了哥德尔为什么只把“哥德尔论题”或是“丘奇论题”看做助探原理而不能享有和图灵论题同等的地位。作为概念分析的典范，图灵论题也为概念实在论提供了一个非常正面的支持。诚然，要从这个范例得出概念实在论的一般立场，以及反过来如何从这个立场出发证明CTT不仅仅是个定义或工作假设从而验证哥德尔对图灵论题和丘奇论题看法的正确性，这需要我们对哥德尔的概念实在论及其哲学做出更系统性的考察，需另行撰文讨论。

《理性》

《当下的启蒙》

《心智探奇》

《思想本质》

《语言本能》

《白板》

本文选自《自然辩证法通讯》2022年第44卷第11期