图灵 vs 哥德尔：可计算性与不完备性

对话背景#

这场对话是反事实编排。库尔特·哥德尔（Kurt Gödel, 1906–1978）与艾伦·图灵（Alan Turing, 1912–1954）从未见面。图灵 1936 年秋到普林斯顿，本想遇见哥德尔；哥德尔 1935 年第二次访问高等研究院后因病离开。罗宾·甘迪后来也证实：老师没有见过哥德尔。把两人写成同桌，是为了把一条哲学压力说清楚——心灵是不是机器——而不是补一场高等研究院的会谈。

1931 年哥德尔证明：足够强的一致形式系统里，有真而不可证的句子；这样的系统也不能在内部证明自己一致。1936 年图灵用一种只有有限内部状态、在纸带上读写的机器，给“有限手续”一个分析，并证明不存在判定任意一阶公式是否可证的一般手续。后人所称的停机问题，是同一条界限的机器说法。数学细节属于另一条文献线索。本篇要问的是：人“看见”不可证的真，是否已经越出任何一台有限机器。

第一幕：什么是可计算的？#

图灵：哥德尔先生，我把计算写成一种极端贫乏的劳动：纸带、读写头、有限的指令表。能用有限步骤做完的事，都能被这样一台机器做完。贫乏是故意的。若连这种装置都做不到，就不是“再聪明一点的工程师”能补上的。

哥德尔：你把“可计算”从日常语感里拖出来，变成可以证明其界限的概念。这一点我后来承认：几条路通向同一个函数类，最令人满意的，是化归为只有有限多个零件的机器。丘奇的 λ-可定义、一般递归，外延上与你的机器重合。重合的是类。类是不是就是心灵做数学时所用的全部手续，仍没有被数学本身判决。

图灵：我没有在 1936 年的论文里判决心灵。我只规定：一个实数可计算，当且仅当一台机器能把它的小数一位一位写下来。绝大多数实数写不下来。可定义也不等于可计算。

哥德尔：可证性是可计算性的一个特例。证明必须是可检查的符号序列。规则若不可判定，“证明”一词就垮了。不完备性说的是：规则可判定，真仍然不必等于可证。

第二幕：停机问题#

图灵：后来的人把我当时写的“无环”“合格数”叫成停机问题。意思是：不存在一台通用手续，对任意程序与输入都能判定它是否终会停下。证明用对角线。假设有 H，能判定任意程序在任意输入上是否停机。再造 D：若 H 说“P 对 P 停机”，D 就永远转；若 H 说不停，D 就停。问 D(D)，两种答案都炸。

哥德尔：自指再次工作。我让句子说“我不可证”；你让机器去审自己的描述。若 H 存在，算术的真就可以被一台机器搜完——那会与不完备性打架。

图灵：打架的层次不同。你谈一个固定系统里的真与可证；我谈所有有限手续的极限。没有通用的停机判官，并不自动告诉我们应该怎样谈人的直觉。

哥德尔：对。定理停在手续。把定理读成“人不是机器”，需要额外的哲学步骤。我后来愿意走这步，但走的时候必须把步骤写出来，不能让 1931 年的论文替我走完。

第三幕：不完备性定理#

哥德尔：我造句子 G，它在系统里等价于“G 不可证”。系统若一致，G 不可证；按构造，G 所说为真。真比可证宽。宽出来的那一截，不是心理状态，是算术事实。

图灵：人怎么“看见”G 为真？看见，常常只是换了一张更强的表：把原系统的一致性加进去，G 就变成可证。1938 年我的博士论文做序数逻辑，就是沿这条路往上加。不完备性没有被取消，只是被推到下一步。

哥德尔：加表的人必须认出下一公理仍然显然为真。认，是否仍是有限手续？若认序数已经超出图灵机，心灵就越出了机器；若整条链仍可被一台机器编码，我们只是把不完备推迟了。

图灵：人也会加错。把“看见”说成永远可靠的光照，我没有证据。我有的是：给定任何一台固定机器，都能造出它答不出或一答就错的问题。人面对自己目前的方法，同样会失败。

第四幕：自指的悖论#

图灵：说谎者说“这句话是假的”。我们都借用了自指，却没有掉进悖论。差别在于把“真”换成可检查的东西：可证，或停机。

哥德尔：论文第一节特意分开。说谎者用了语义上的“真”；我只用语法上的“可证”。语法可以写成算术谓词。没有算术化，自指只是句子游戏。

图灵：通用机器让游戏变成装置。一台机器读入另一台的标准描述，就模拟它。正因为它通用，它不能充当自己的合格性判官。通用不是全能。全能是宣传语言。

哥德尔：编码把自我指涉从修辞变成定理。定理不自动变成关于意识的神学。谁若在这里直接写入灵魂，是他自己写入的。

第五幕：数学的基础#

哥德尔：我是柏拉图主义者。自然数、集合、证明关系，并不因为被写在纸上才存在。系统若一致，G 在标准模型里为真，却不能被该系统证明。这个“更宽”要求真有一个独立于推导的着落。

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

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

图灵：析取是诚实的。诚实之处在于：不完备性单独推不出“心灵不是机器”。要推出这一句，还得加上“人不会在算术上永远卡住”之类的前提。我不愿把这前提当成已经证明的事实。

第六幕：机器与心灵#

图灵：1950 年《计算机器与智能》把“机器能思维吗”换成模仿游戏。审讯者只通过文字，区分隔壁是人还是机器。若机器经常让人判错，我们就没有好理由拒绝说它在思维。这是把问题从本质改成可观察的行为。文章里单独回答了“数学异议”：哥德尔一类结果表明，任意一台给定的机器总会遇到答不出或一答就错的问题。可是人也会。把“人能看见 G 为真”说成“人超越一切机器”，忽略了：人看见的是针对那一台机器的 G。换更强的系统，又有新的 G'。

哥德尔：行为测试过关，并不等于心灵被穷尽。固定的图灵机对应于固定的形式系统。若人的全部数学产出恰好等于某台有限机器的产出，析取的第二支就会逼近：存在人永远判不了的算术问题。我不愿接受人被关在这样一个房间里。

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

哥德尔：原则与工程要分开。不完备性不是工程预算。它不禁止机器证出许多定理；它禁止把“全部对心灵显然的公理”装进任何一张有限、固定的表。若改表的规则仍有限，整条链还是一台机器。真正的问题是有没有这样一条有限规则。

第七幕：人工智能的极限#

图灵：若明天有一台装置通过了模仿游戏，你仍要说它不理解吗？

哥德尔：理解若只是输出与人不可分，我可以说：那只是行为。数学直觉是看见符号所关于的那种对象。对象不属于纸带。1972 年前后我对王浩说过更谨慎的话：就已证明的而言，仍可能存在一台实际上与数学直觉等价的定理证明机，只是无法证明它如此，也无法证明它只产出正确的有限算术。谨慎不是撤退。它说明：反机械论不是 1931 年定理的推论，是定理加上理性主义态度之后的哲学选择。

图灵：选择可以公开。公开之后，就不能再把选择说成定理。我列过“各种无能”：无意识、无审美、不能真正创新。这些话很难检验。模仿游戏至少给出一个场。场可以作废。作废也必须提出新的可观察标准，而不是把“真正理解”当成永远无法输掉的底牌。

哥德尔：底牌若永远无法输掉，它就不是论证。我停在析取上。第一支成立，则心灵超过任何有限机器；第二支成立，则存在人永远判不了的算术问题。未来是在两支之间做更细的形式工作，而不是提前宣布其中一支已经赢了。

第八幕：数学的未来#

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

哥德尔：不完备性保证这张分工表没有最后一行。任何一台固定的定理证明机，都留下它自己的 G。对柏拉图主义者，这是理念世界深于纸面系统的证据；对机器理论，这是通用机器不能充当自身合格性判官的证据。两种读法共用一条证明。

图灵：共用证明，不共用本体论。我死于 1954 年，看不到此后的装置。把 1950 年的模仿游戏读成对后来任何系统的神谕，是错的。我给出的是一个行为标准，以及一份对常见异议的逐条回答。

哥德尔：我也不把吉布斯讲演读成神谕。讲演自己说：不要期待这些推论有数学的严格。谁用它给所有未来的机器盖棺，谁就比我更独断。

第九幕：遗产#

图灵：我们的定理画出同一条界限。界限不是“再聪明一点就能跨过去”的技术障碍，而是手续概念自身的结构。个人命运是另一件事。我因同性恋身份被化学阉割，1954 年死去。那不能拿来给定理加注。

哥德尔：我晚年深陷被迫害的恐惧，1978 年在普林斯顿死于饥饿。那同样不能拿来给析取加注。思想可以被悲剧照亮，也可以被悲剧感伤化。感伤化之后，机器与心灵的问题看起来像一出道德剧。它不是。它是：人是否在数学上无限超过有限机器。答案若有，也应是论证，不是悼词。

图灵：卢卡斯 1961 年、彭罗斯 1989 年把不完备性读成“意识非算法”。那是他们的论证，有自己的漏洞与辩护。不是我的 1950 年，也不是你的 1931 年。把后人的结论塞进我们嘴里，会让这场本不存在的对话更加不存在。

哥德尔：同意。我们从未对坐。对坐之后若还要有一句可带走的话，就只这一句：不完备性限制的是固定的形式系统与固定的机器；心灵是否落在这个限制之内，仍是一个未被定理关闭的问题。

分析#

哥德尔的不完备性与图灵对判定问题的否定，共用对角线和自指，指向的层次却不同。前者说：足够强的系统既不能穷尽算术真理，也不能在内部证明自己一致。后者说：不存在判定任意机器是否停机、从而也不存在判定任意一阶公式是否可证的一般手续。本篇不把这两条证明再展开一遍。它要分开的是：定理所限制的对象，与后来被安到两人头上的心灵学说。

两人从未在普林斯顿碰面。常见捷径“若心灵等于图灵机则心灵应当完备，故心灵不是机器”并不成立。哥德尔 1951 年写下的是析取，并承认未证明第一支；对王浩的谨慎补充进一步说明，等价于直觉的机器在逻辑上仍未被排除。图灵 1950 年对“数学异议”的回答是：人也会失败，而且可以通过加强系统前进。卢卡斯—彭罗斯把不完备性读成意识非算法，已超出两人论文愿意担保的范围。

最深的分歧因此不在纸带的定义，在“看见真”要不要一种非手续的能力。图灵把思维当作可在模仿游戏里检验的行为，把“人看见 G”解释成换了一张更强的指令表。哥德尔把数学对象当作独立于心灵的实在，把不完备性读成：真比任何一张有限表更宽；心灵是否超过有限机器，则停在吉布斯讲演的析取上。

核心分歧#

人类心灵是否可以被算法完全模拟？图灵认为：若思考可以用手续描述，机器就可以执行；模仿游戏通过之后，再坚持“没有真正理解”，必须提出新的可检查标准，而不能只靠定义取胜。哥德尔认为：人可以站在一个形式系统外面承认其一致性，从而看见该系统的 G 为真；若人的全部数学能力等于某台有限机器，就会逼近存在人永远判不了的算术问题。他倾向心灵超过机器，并把这一倾向写成需要额外前提的哲学选择，而不是 1931 年的推论。

当代启示#

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

延伸思考#

• 哥德尔 1951 年的析取，哪一支更难被经验或形式工作触动？若我们拒绝“存在对人绝对不可解的算术问题”，是否已经在暗中选择了心灵超过机器？
• 图灵的序数逻辑是否只是把不完备性推迟到“认序数”的步骤上？认出下一公理为真，还是不是有限手续？
• 模仿游戏通过之后，还要不要单独保留“理解”这个词？若要保留，检验它的标准是什么——若没有任何标准，这个词是否只是人类中心的禁令？

延伸阅读：图灵《论可计算数》(1936/1937)；图灵《计算机器与智能》(1950)；哥德尔《论形式不可判定命题》(1931)；哥德尔 1951 年吉布斯讲演，见 Collected Works 第三卷；王浩《A Logical Journey》(MIT, 1996)；卢卡斯 “Minds, Machines and Gödel”(1961)；彭罗斯《皇帝新脑》(1989)