1936：图灵证明没有一般过程能判定机器是否无圆

破除误解：无圆不是停机，1937 年也不是这篇的发表年#

第一层误解把论文读成「图灵在 1936 年把问题命名为停机问题」。正文没有使用后来教科书的英文术语 halting problem，也没有把装置称作图灵机。论文的词是 computing machine。它证明的是：不存在一般过程，能在有限步内判定任意一份标准描述是不是无圆机器。停机问题的后来表述是另一句：给定机器和输入，计算会不会停下。两句都不可判定。后一句问某一次计算有没有终点。前一句问第一类符号会不会被无穷次印出来。一台机器可以永远走下去，却从某一步起只印草稿、不再印第一类符号，论文仍记为有圆。另一台可以永远走下去并不断印出 0 和 1，论文记为无圆。用停机的词汇去套，无圆机器落在「不停」的那一侧里仍在产出序列的那些。两句不能互换。

第二层误解把无圆听成「会停」，或把有圆听成「还在印所以不算停」。分界只看第一类符号的个数。第一类符号是写入序列的数字，论文取 0 和 1。第二类符号是草稿，可以印很多，却不计入序列。有圆包括两种：走进没有后继的格局，动作因而停止；或者还在动，甚至继续印第二类符号，但再也印不出新的第一类符号。无圆不是停在一个答案上，而是把 0 和 1 无穷地印下去。把无圆理解成停机，会把要判定的性质反转。

第三层误解把发表年收成 1937。目录上的这个年份，来自卷期所标的 1936–37，以及更正本身出在 1937。收到与宣读仍在 1936，正文仍是第 42 卷 230–265 页。把更正说成整篇的发表年，会让正文和勘误变成同一件事。

第四层误解把阿隆佐·邱奇（Alonzo Church）的证明和这篇焊成同一次投稿。论文开篇写明：邱奇在近作里提出的 effective calculability 与这里的 computability 等价，定义却很不相同。邱奇对判定问题也得到相近结论。等价的证明只在本篇附录里给了提纲，把 λ 可定义序列与机器所算的序列对到一起。提纲不是邱奇论文的复述。邱奇的不可判定结果写在他自己的 1936 年论文里。本页只记录图灵承认等价、同时声明定义不同。后来的「邱奇–图灵论题」是事后的合称，不是这页纸上的标题。

第五层误解把「没有一般过程」听成「还没找到算法」，或听成「机器太慢」。第 8 节把「存在一般过程」等同于「存在一台会做这个判定的机器」。若每个描述数都能在有限步内判完，这个判定本身就可以写成一条 0 和 1 的序列。否定的是这台机器的存在，不是某一台物理装置的速度或内存。

标准描述、无圆，以及第 8 节的对角线#

装置从按规则演算的人开始，不是从后来的处理器开始。纸带分成格子，每一时刻只看一格。有限的表根据当前状态和读到的符号，决定印什么、向左或向右或不动，以及下一步进入哪个状态。某一阶段的完整格局，由正在看的格子、整条纸带上的符号和当时的状态合在一起描述。相邻两个完整格局之间是一步。第一类符号进入序列，第二类符号留在草稿里。序列称为可计算的，若有一台无圆机器把它印出来。一个数称为可计算的，若它和某个无圆机器算出的数只差一个整数。论文后面更多谈论序列，以免和数纠缠。

有圆与无圆就钉在第一类符号的个数上。从未写下多于有限个第一类符号的机器叫做有圆，否则叫做无圆。没有后继格局会有圆。继续移动却不能再印第一类符号，也会有圆。circular 这个词为什么这样叫，论文留到第 8 节：自指的那一段会转不出去。无圆机器要印出无穷序列，因此在「会不会停下」的问法里，它不是停下的那一种。

要说「任意一台机器」，先得把机器表收成自然数。每一行写成一条指令，行与行用分号隔开。状态下标 i 换成字母 D 后跟 i 个 A，符号下标 j 换成 D 后跟 j 个 C。这样的标准描述（standard description）只含 A、C、D、L、R、N 和分号。再把 A 换成 1、C 换成 2、D 换成 3、L 换成 4、R 换成 5、N 换成 6、分号换成 7，读出的自然数称为描述数。无圆机器的描述数，论文叫做 satisfactory number，也就是合格描述数。第 8 节证明：不存在一般过程判定一个给定的数是否合格。这套替换是论文给机器的命名法，不是一门语言的语法，也不是让人照着做判定器的工序。

通用机器在第 6 节和第 7 节已经定义。给定标准描述，它能逐步做出那台机器的动作，并把新出现的第一类符号印出来。第 8 节需要的只有这件事。本页不抄它的行为表，也不说明怎样用它去算一个指定的数。没有它，归谬缺一块。有了它，对象仍然是判定，不是通用机器本身。

第 8 节先拆掉一种会把结论说歪的对角线。假如可计算序列已经排好，第 n 条的第 m 个第一类符号记为序列中的那一位，再造一条新序列，其第 n 位取成与第 n 条的第 n 位不同的符号，也就是 0 与 1 对换。新序列和每一条都至少差一位，看起来可计算序列就不可枚举。漏洞在于假定了新序列本身可计算。它可计算，只有当全部可计算序列能用有限手段枚举出来，而这等价于判定一个数是不是某台无圆机器的描述数。论文要证明的正是不存在这种有限步内的一般过程。描述数取自自然数，机器表至多可数。被否定的不是康托尔意义上的可数，而是有一台无圆机器把全部可计算序列排出来。把这则谬误当成定理，会把「不能有限枚举」说成「可计算序列多得像实数」。

真正的归谬不去造那条对换后的序列，以免读者觉得对换本身偷偷假定了不该假定的东西。假定存在一台判定机：给它任意机器的标准描述，有圆标 u，无圆标 s，并且每个记号都在有限步内写下。把它和通用机器合起来，设想一台产出序列 β′ 的机器。它按 1、2、3 检验自然数。到 N 时，若 N 不合格，β′ 不添新的一位。若 N 合格，就数出到 N 为止有多少个合格描述数，用通用机器算出以 N 为描述数的那台机器的同样多个第一类符号，把最后一位写入 β′。判定在有限步内给出。N 若合格，对应机器无圆，那一位也在有限步内出现。于是每一段都结束，合起来的机器本身无圆。

设这台机器自己的描述数是 K。轮到 K 时，两个记号都不成立。不能标 u，因为按上一段它无圆。不能标 s，因为标 s 就要求它写出「描述数为 K 的那台机器」的下一位第一类符号，而那台机器就是它自己，这一位又正是此刻要写、却还没有写出的符号。指令变成向自己索取尚未出现的一位，这一段结束不了，机器又成为有圆。既不能是 u，也不能是 s。因此能给每一份标准描述打上无圆或有圆的判定机不存在。合起来的机器只出现在归谬里，不是可以拿去运行的判定手续。

第 8 节把「有一般过程」等同于「有一台机器在有限步内做完这件事」，并说明这个同义要以论文对可计算的定义站得住为前提。同义本身不是一份判定手续。

它没有命名停机问题，没有解决判定问题，也没有给出编程语言#

它没有把问题命名为停机问题。1936 年的句子是否定无圆判定，也就是否定合格描述数的判定。后来的句子是否定「机器加上输入之后会不会停下」。同属不可判定，只说明两边都没有对一切实例都在有限步内答对的手续，不说明两句同一难度，更不说明论文做了这个翻译。停下看有没有终点。无圆看第一类符号是否被无穷次印出。不能把后一句回写成这一年的原句。

它没有解决判定问题。第 11 节把第 8 节用到希尔伯特的 Entscheidungsproblem：对狭义函数演算中的一个公式，有没有一般过程判定它能否被证明。结论是这个判定问题没有解。方向是归谬。若可证性能被一般过程判定，就可以由此判定一台机器是否无圆，与第 8 节冲突。没有解，意思是不存在判定手续，不是说公式变得没有意义，也不是说每一个具体公式都永远无法证明。专门的公式仍可以有专门的证明。被否定的是吃进任意公式、并在有限步内回答可证或不可证的那一种过程。把「没有解决」听成「论文没做完，问题还开着」，会把否定定理读成未完成的作业。把它听成「已经给出判定算法」，方向又反了。

1937 年的更正不把这个否定改成肯定。更正写明，狭义函数演算的判定问题不可解，原文证明含有形式错误，保罗·贝尔奈斯（P. Bernays）指出了这些错误。更正改写相应的形式翻译，并说明改过之后证明成立。它也改写若干作者认为原文并不为假、但应当修改的陈述，包括可计算数怎样对应到序列。这些修改在第 43 卷 544–546 页。它们不是第 42 卷的重刊，也不把 230–265 页的发表年改到 1937。第 8 节关于无圆的否定，不是更正要撤回的部分。

它没有给出编程语言。标准描述是给已经写好的机器表换一套字母和数字，以便谈论「全部机器」。通用机器说明一份描述可以被另一台机器读进去执行。这是数学对象之间的关系，不是语法手册，没有源文本和编译的规定，也没有存储程序计算机的工程规格。1936 年做计算的 computer，仍是按有限规则在纸上演算的人。机器是这个人的理想化。后来的程序语言可以表达同一类过程，那是事后的对应。从这篇里读不出一门语言，也读不出如何实现停机判定器。判定器不存在，正是第 8 节的结论。

它也没有把「人用有限手段算得出的，机器都能算」证明成与第 8 节同类的定理。第 9 节写明，哪些数应当算作可计算，这类论证要诉诸直觉。那是论题的位置。第 8 节是模型内部的否定：不存在判定无圆的那一台。覆盖范围被人争论，也不取消这个内部否定。本页停在这个分界上，不把论题再写成总览。

跨域连接#

• 可计算性：总览用后来的停机句子给不可判定性一个入口，并铺模型与层次。本页只提供 1936 年印出的那一句：没有一般过程判定无圆。叠读时，总览里「给定程序和输入，问会不会停」应看成同属不可判定的后代表述，不是第 42 卷的原句。论文用的词是第一类符号、标准描述，以及和第 8 节里通用机器合在一起的归谬。
• 哥德尔不完备定理：论文说第 8 节的结论表面上类似哥德尔。类似处是自指。哥德尔 1931 年构造一个说自己不可证的算术句子。图灵假定一台能给一切标准描述打上 u 或 s 的机器，它在自己的描述数上两个记号都接不住。一个打击形式系统的完备，一个打击对无圆的一般判定。形状相近，对象不同。两边的失败都不等于每一个具体实例都没有专门的证明或理由。
• 康托尔定理：第 8 节借用对角线，又限制用法。康托尔说明一条已经排好的序列盖不住全部对象。图灵指出：若不存在有限手段枚举可计算序列，对换后的新序列就不能算作可计算，因此推不出这些序列不可数。描述数是自然数，机器表至多可数。本页的对角线制造判定机对自己的矛盾，不是把康托尔定理抄成计算版。
• 希尔伯特第十问题：第十问题要一条手续，判断任意整系数多项式有没有整数根，否定答案到 1970 年才补齐。第 11 节要的是另一条手续，判断狭义函数演算里任意公式能否被证明，否定写在 1936 年。输入一个是多项式，一个是逻辑公式。都叫判定问题，并不共用实例，也不能互相把年份提前。
• 证明：无圆判定的否定是一条反证，不是一批失败的试算。假定判定机存在，再与通用机器合在一起，就得到一台在自己的描述数上写不下一位的机器，假定因此取消。1937 年的更正说明形式翻译可以写错。贝尔奈斯指出错误之后，改写的仍是证明，不是改口说判定手续存在。个别机器上的成功检验，填不满对一切标准描述的那个量词。
• 认识论：论文把一般过程收成一台在有限步内写完记号的机器，于是「有没有办法知道」变成「有没有这台机器」。第 9 节把另一件事留在外部：凭什么说人用有限手段能算的都落进这些机器，作者明说这要诉诸直觉。知道某一台具体机器无圆，可以来自对那张表的阅读。知道每一台是不是无圆，则被第 8 节否定。把后一种当成已经拥有的一般能力，会和描述数上那两个不可能的记号冲突。

参考文献#

• A. M. Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, series 2, 42 (1936–37), pp. 230–265. Received 28 May 1936. Read 12 November 1936. DOI: 10.1112/plms/s2-42.1.230. —— 本文对象。文首日期在 1936。第 8 节证明没有一般过程判定机器是否无圆。第 11 节用于判定问题，结论是没有解。后来有的目录把发表年盖成 1937，本页不采纳。
• A. M. Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction", Proceedings of the London Mathematical Society, series 2, 43 (1937), pp. 544–546. —— 1937 年的是这份更正。它处理贝尔奈斯指出的形式错误，不把第 42 卷重订为 1937 年发表。
• B. Jack Copeland, ed., The Essential Turing, Oxford University Press, 2004. —— 刊期说明：两个部分都在 1936 年印出，卷期标 1936–37。把整篇发表日期改成 1937 是不正确的。
• Alonzo Church, "An Unsolvable Problem of Elementary Number Theory", American Journal of Mathematics 58 (1936), pp. 345–363. —— 邱奇自己的论文。有效可计算性在这里另有定义，不与图灵这篇收成同一次证明。
• Alonzo Church, "A Note on the Entscheidungsproblem", Journal of Symbolic Logic 1 (1936), pp. 40–41. Correction: Journal of Symbolic Logic 1 (1936), pp. 101–102. —— 邱奇对判定问题的结论在这一则里，先于图灵 1936 年 11 月 12 日的宣读。图灵只注明结论相近、定义不同。
• Kurt Gödel, "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I", Monatshefte für Mathematik und Physik 38 (1931), pp. 173–198. —— 论文所说「表面上类似」的那一项。对象是不可证的算术句子，不是无圆判定。
• David Hilbert and Wilhelm Ackermann, Grundzüge der theoretischen Logik, Springer, 1928. —— 第 11 节所针对的问题：狭义函数演算中，任意公式是否可证。