哥德尔 vs 图灵：不可判定性

对话背景#

库尔特·哥德尔（Kurt Gödel, 1906–1978）于 1930 年 11 月 17 日把论文投给《数学与物理月刊》。1931 年刊出的《论〈数学原理〉及有关系统中形式上不可判定的命题 I》（Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I，第 38 卷，第 173–198 页）给出两个核心结果：定理 VI——任何满足一定条件的形式系统中都有不可判定命题；定理 XI——这样的系统若一致，就不能在内部证明自身的一致性。系统 $P$ 以怀特海与罗素的《数学原理》为骨架，再装上皮亚诺算术。

艾伦·图灵（Alan Turing, 1912–1954）的《论可计算数及其在判定问题上的应用》（On Computable Numbers, with an Application to the Entscheidungsproblem）1936 年 5 月 28 日收稿，11 月 12 日在伦敦数学会宣读，1937 年正式刊出。他定义了后来称为图灵机的 $a$-机器，证明可计算数列可数、却不存在判定一台机器是否「无环」（circle-free）的一般手续，并由此推出希尔伯特的判定问题无解。丘奇用 $\lambda$-可定义性先一步发表了否定解答；图灵在附录里补上两种定义的等价。

两人从未见面。图灵 1936 年秋到普林斯顿，本想遇见哥德尔；哥德尔 1935 年第二次访问高等研究院后因病离开。本对话依据双方已发表的论文与讲演立场，不是一次史料中的会谈。

第一幕：不可判定命题#

哥德尔：图灵先生，我的第一不完备定理——论文里的定理 VI——说的是：任何一个足够强、又满足递归可枚举等条件的一致形式系统，都含有不可判定命题。存在一个命题 $G$，使得 $G$ 与 $\neg G$ 都无法在该系统内推出。

图灵：你怎样造出 $G$？

哥德尔：先把符号、公式、证明编成自然数，现在叫做哥德尔数。关于「可证」的语法谓词，于是变成算术里的一个关系 $\mathrm{Bew}(x)$。然后造一个句子 $G$，它在系统里等价于「$G$ 的哥德尔数不在可证关系里」。若 $G$ 可证，系统就不一致；若系统一致，$G$ 便不可证，而按构造 $G$ 所说为真。论文第一节把这件事写成：用「我不可证」代替说谎者的「我为假」，从而擦过悖论、落到定理上。

图灵：我的 1936 年论文第 8 节也用了对角线，目标不同。机器由有限指令表决定；把标准描述换成数字，得到描述数。能不断印出 0 与 1 的机器是无环的，其描述数叫合格数。可计算数列由无环机器印出，因而可数。若存在判定合格数的一般手续，就可以枚举可计算数列，再沿对角线造 $\beta$。$\beta$ 会与每一行都不同，却又该可计算——矛盾。错不在对角线，而在「$\beta$ 可计算」这个假定。第 11 节由此推出：不存在对谓词演算 $K$ 的任意公式 $U$ 判定其是否可证的机器。判定问题无解。我在文中写过：所证之事与您 1931 年的结果只是表面上相似。

哥德尔：相似之处是自指和对角线。不同之处是：我谈的是一个固定形式系统里的真与可证；你谈的是所有有限手续的极限。

第二幕：可计算性与可证明性#

图灵：判定问题比单个系统的不完备更宽。希尔伯特与阿克曼 1928 年把一阶逻辑的判定问题写清楚：要一台对任意公式都能回答「可证还是不可证」的手续。丘奇 1936 年用 $\lambda$-演算先给出否定答案。我当时在剑桥，并不知道他的稿子；纽曼把丘奇的论文给我看之后，我在附录里证明：我的可计算性与 $\lambda$-可定义性刻画同一类函数。

哥德尔：1934 年我在高等研究院用赫尔布兰的提示定义了一般递归。丘奇要把「能行可计算」直接等同于 $\lambda$-可定义或一般递归，我当时觉得不能令人满意——那更像论题，不是从「有限手续」里分析出来的。你把手续写成只有有限内部状态、在纸带上读写的机器，这个分析后来让我接受了同一外延。吉布斯讲演里我写过：几条路通向同一个概念，最令人满意的是化归为你那种只有有限多个零件的机器。

图灵：机器语言不必先相信一套方程推演。纸带、状态、打印，对应人用铅笔在方格纸上算。第 9、10 节争辩：$\pi$、$e$、代数数的实部，凡「自然会被看作可计算」的都落在这个类里。类很大，却仍可数，因而绝大多数实数不可计算。可定义也不等于可计算。

哥德尔：可证性是可计算性的一个特例。一个命题在系统里可证，当且仅当存在有限长的符号序列满足推理规则。规则本身必须是可判定的，否则「证明」一词就失去检查手续。不完备性说的是：即便规则可判定，真命题的集合仍不必与可证命题的集合重合。

图灵：所以停机——用后来的话说——比不完备更「低」。若合格数可判定，就可以机械地搜证明；您的不可判定句子就不会存在。反过来，不完备并不自动给出判定问题的否定，因为一阶逻辑的公式比算术句子更宽，而丘奇和我要拦的是「所有公式」这一层。

第三幕：自指的悖论#

图灵：两条证明都让一个对象谈论自己。这让人想起说谎者，也让人想起理查德悖论：用自然语言枚举可定义实数，再沿对角线造一个「不可定义」的定义。

哥德尔：论文第一节特意分开。说谎者用了「真」这个语义概念；我只用「可证」这个语法概念。语法可以在算术里写出来。康托尔的对角线提供骨架；若「可定义」没有被钉成算术谓词，对角线会重新变成悖论而不是定理。

图灵：我这边的自指更具体。通用机器 $U$ 读入任意机器的标准描述，就模拟那台机器。把 $U$ 和一台合格数判定机接在一起，再问这台组合机器自己的描述数，循环与无环两个判决都不可能。正因为它通用，它不能充当自己的合格性判官。

哥德尔：编码是关键。我把证明变成数，您把机器变成数。没有算术化，自指只是句子游戏。

第四幕：数学的基础#

哥德尔：图灵先生，你认为数学对象是被发明的，还是被发现的？

图灵：1936 年的论文不回答这个。它只规定：一个实数可计算，当且仅当一台无环机器能把它的小数一位一位写下来。至于不可计算的实数「存在」的方式，我满足于说：它们不能被任何有限手续接触。数学家日常的工作，大部分是符号上的有限变换。

哥德尔：我是柏拉图主义者。自然数、集合、证明关系，并不因为被写在纸上才存在。不完备性加强了这一点：一个系统若一致，$G$ 在标准模型里为真，却不能被该系统证明。真比可证更宽。这个「更宽」不是心理学，是算术事实。

图灵：我可以接受「真比可证更宽」，而不必接受先于人类的理念世界。机器枚举可证句子，枚举不完所有真句子。这是关于手续的定理，不必先谈理念。

哥德尔：1951 年吉布斯讲演把哲学推论写成析取，并声明当时的哲学还不能把它做成数学那样的严格：要么心灵——即便限于纯数学——无限超过任何有限机器，要么存在对人而言绝对不可解的丢番图问题。我倾向第一支，并未证明它。第二支会让希尔伯特「每个明确问题都可判定」落空，那种理性主义我不愿轻易放弃。

图灵：1950 年《心智》上我回答过「数学异议」。哥德尔一类结果确实表明：任意一台给定的机器总会遇到答不出或一答就错的问题。可是人也会。把「人能看见 $G$ 为真」说成「人超越一切机器」，忽略了：人看见的是针对那一台机器的 $G$。换更强的系统，又有新的 $G'$。

第五幕：机器与心灵#

图灵：1950 年那篇《计算机器与智能》把「机器能思维吗」换成一个可操作的问题：模仿游戏。审讯者只通过文字，区分隔壁是人还是机器。若机器经常让人判错，我们就没有好理由拒绝说它在「思维」。这不是神秘主义，是把问题从本质改成可观察的行为。

哥德尔：行为测试过关，并不等于心灵被穷尽。不完备性给出的是另一条缝：人可以站在一个形式系统外面，承认它的一致性，从而看见该系统的 $G$ 为真。固定的图灵机对应于固定的形式系统。若人的全部数学产出恰好等于某台有限机器的产出，析取的第二支就会逼近：存在人永远判不了的算术问题。

图灵：同一篇文章里我写了：可以设想一串越来越强的证明机器，每一台多一条公理——例如前一台的一致性。这正是我 1938 年博士论文、1939 年《基于序数的逻辑系统》里做的事。从 $L$ 得到更完备的 $L'$，再沿序数迭代。不完备性没有被取消，只是被推到极限处。人「看见 $G$ 为真」，很像换了一台更强的机器。

哥德尔：序数逻辑是认真的数学。问题在于：沿哪些序数走、如何认出下一公理仍然显然为真，这是否仍是有限手续。若认序数已超出图灵机，析取的第一支更像真的；若整条链仍可被一台机器编码，我们只是把不完备推迟了。

图灵：1950 年文末谈学习机器。纸带不必装满答案，可以留空白让经验去写。劳斯莱斯夫人说机器只能做吩咐它的事；学习机器要回答的正是这条异议。我并不声称当时的数字计算机已经在思维。我声称：没有一条原则禁止将来的机器在模仿游戏里成功。

哥德尔：原则与工程要分开。不完备性不是工程预算。它不禁止机器证出许多定理；它禁止把「全部数学真理」装进任何一张有限、固定的公理表。

第六幕：遗产#

图灵：我们两人的工作从不同角度画出同一条边界。边界不是「再聪明一点就能跨过去」的技术障碍，而是手续概念自身的结构。可计算数可数，一阶逻辑不可判定，算术不能在内部证明自己一致。三条线交在自指上。

哥德尔：这些限制也标明数学有多富。没有任何有限公理表能把算术真理穷尽。对柏拉图主义者，这是理念世界深于纸面系统的证据；对机器理论，这是通用机器不能充当自身合格性判官的证据。两种读法共用一条证明。

图灵：有人把故事讲成：您 1931 年的论文是我 1936 年论文的基础。克莱尼后来写过：丘奇走 $\lambda$-可定义、我走机器，两条根是独立的。1938 年的序数逻辑才真正把您的「著名定理」当作出发点。

哥德尔：独立的根仍可以长成同一外延。一般递归、$\lambda$-可定义、图灵可计算，被证明是同一个函数类。我关心的是这个类是否就是「有限手续」。接受这一点之后，不完备性才获得它最干净的形式：不存在一台图灵机，枚举所有真的算术句子。

第七幕：算法与创造力#

图灵：若心灵等于某台机器，创造力是什么？1950 年我列过「各种无能」：无意识、无审美、不能真正创新。这些话很难检验。模仿游戏至少给出一个场：若表现与人不可分，无能就必须重新定义，而不能只当作定义。

哥德尔：创造力或许是看见当前系统之外的真。这种看见若不能被有限规则穷尽，析取的第一支就成立。我并不声称已经证完。吉布斯讲演特意写下：今日哲学还不允许把这些推论做成数学那样的严格。

图灵：序数逻辑是我能给出的折中。创造力不必一次跳出所有手续：在停住的系统上再加一条可检查的公理，然后继续。人换方法，机器换纸带。差别也许只在谁被允许改自己的表。

哥德尔：改表的规则若仍有限，整条链还是一台机器。真正的问题是：有没有一条有限规则，能生成一切对心灵显然的公理。不完备性把「没有」变成可讨论的数学选项，而不是气质性的宣言。

第八幕：数学的未来#

图灵：战后我在国家物理实验室做 ACE，后来在曼彻斯特参与存程序计算机。1936 年的通用机器不再只是纸上的 $U$。即便如此，选问题、认证明是否真懂、决定下一步加哪条公理，在我能看见的年代仍是人的工作。

哥德尔：合作是可能的。机器做检查，人给出新公理与意义。不完备性保证这张分工表没有最后一行。任何一台固定的定理证明机，都留下它自己的 $G$。

图灵：我死于 1954 年，看不到此后的机器。把 1950 年的模仿游戏读成对后来任何装置的神谕，是错的。我给出的是一个行为标准，以及一份对常见异议的逐条回答。标准可以作废。

哥德尔：心灵与机器的关系，我仍只愿停在那个析取上。第一支成立，则心灵超过任何有限机器；第二支成立，则存在人永远判不了的算术问题。未来是在两支之间做更细的形式工作，而不是提前宣布其中一支已经赢了。

分析#

哥德尔 1931 年的定理 VI 与 XI，和图灵 1936 年关于合格数与判定问题的否定解，共用对角线和自指，指向的层次却不同。前者说：足够强的形式系统既不能穷尽算术真理，也不能在内部证明自己一致。后者说：不存在判定任意机器是否无环、从而也不存在判定任意一阶公式是否可证的一般手续。丘奇的 $\lambda$-演算与图灵的机器外延相同；哥德尔起初拒绝把「能行可计算」等同于 $\lambda$-可定义，后来把图灵的有限零件分析称作最令人满意的一条路。

两人从未在普林斯顿碰面。把「停机问题」一词塞回 1936 年的口中也不准确：图灵写的是无环、合格数、判定问题。常见捷径「若心灵等于图灵机则心灵应当完备，故心灵不是机器」也不准确。哥德尔 1951 年写下的是析取，并承认未证明第一支。图灵 1950 年对「数学异议」的回答是：人也会失败，而且可以通过加强系统前进。卢卡斯—彭罗斯把不完备性读成「意识非算法」，已超出两人论文愿意担保的范围。

核心分歧#

最深的分歧不是技术，是对「看见真」的解释。图灵把思维当作可在模仿游戏里检验的行为，把「人看见 $G$」解释成换了一张更强的指令表。哥德尔把数学对象当作独立于心灵的实在，把不完备性读成：真比任何一张有限表更宽；心灵是否超过有限机器，则停在吉布斯讲演的析取上，并不宣称已经证完。

当代启示#

大语言模型能生成看似「懂数学」的文本之后，这场争论常被当成口号。图灵死于 1954 年，不能对后来的装置表态；他留下的是 1950 年的行为标准。哥德尔留下的是 1951 年的析取，不是「任何通过行为测试的系统都缺乏元层次洞察」这种全称句。固定的公理表与固定的图灵机都有自己的 $G$；若系统被允许改自己的公理，必须先问「改」是否仍是有限手续。彭罗斯《皇帝新脑》属于后期文献，不是 1931 或 1936 年论文的推论。

延伸思考#

• 哥德尔 1951 年的析取，哪一支更难被经验或形式工作触动？
• 图灵的序数逻辑是否只是把不完备性推迟到认序数的步骤上？
• 模仿游戏通过之后，还要不要单独保留「理解」这个词？

延伸阅读：哥德尔《论〈数学原理〉及有关系统中形式上不可判定的命题 I》(1931)；图灵《论可计算数及其在判定问题上的应用》(1936/1937)；图灵《基于序数的逻辑系统》(1939)；图灵《计算机器与智能》(1950)；哥德尔 1951 年吉布斯讲演，见 Collected Works 第三卷；戴维斯编 The Undecidable (1965)