https://link.springer.com/article/10.1007/s00283-022-10177-y

Published: 04 June 2022

Did Turing Stand on Gödel’s Shoulders?

B. Jack Copeland & Zhao Fan 

图灵是站在哥德尔的肩膀上吗？- B. Jack Copeland & Zhao Fan 

The history of mathematics is a field generally characterized by careful scholarship and close attention to evidence. Sometimes, though, a story with little or no evidence in its favor takes root and propagates. We discuss a case in point. It is widely maintained in the literature that Kurt Gödel’s 1931 work on incompleteness was the foundation for Alan Turing’s work on computability and undecidability, set out in his famous 1936 paper “On Computable Numbers” (OCN) [45]. (See Figures 1 and 2 for photographs of our two lead characters.) In fact, there is very little evidence for this contention. The aim of our discussion is to arouse a skeptical attitude toward this often-repeated claim, and we hope in future to see the claim treated with greater caution in the literature.

数学史是一个以严谨的学术研究和密切关注证据为特征的领域，但有时一个几乎没有证据支持的故事却能扎根并广为传播，我们来讨论一个这样的例子。文献中普遍认为，库尔特·哥德尔 1931 年关于不完备性的工作是艾伦·图灵关于可计算性和不可判定性工作的基础，后者在他 1936 年的著名论文《论可计算数（On Computable Numbers）》（OCN）中有所阐述 [45]。（见图 1 和图 2 中两位主角的照片。）事实上，支持这一论点的证据很少，我们讨论的目的是唤起人们对这一经常重复的说法持怀疑态度，我们希望未来文献中能更加谨慎地对待这一说法。

OCN is widely regarded as a founding document—perhaps the founding document—of computer science. This “seminal paper,” says Turing Award laureate Vinton Cerf, introduced “key concepts … that continue to play a central role in our industry today.” Furthermore, the undecidability results that Turing proved in OCN are, along with Gödel’s 1931 incompleteness theorems, major milestones in twentieth-century mathematical logic.

OCN 被广泛视为计算机科学的奠基文献，或许是奠基文献。图灵奖获得者 Vinton Cerf 称，这篇“开创性论文”引入了“关键概念……至今仍在我们的行业中发挥核心作用”。此外，图灵在 OCN 中证明的不可判定性结果与哥德尔 1931 年的不完备性定理一起，是 20 世纪数理逻辑的重要里程碑。

Gödel repeatedly praised OCN and made fundamental use of Turing’s ideas. He emphasized that “due to A. M. Turing’s work, a precise and unquestionably adequate definition of the general concept of formal system can now be given,” with the consequence, he said, that incompleteness can “be proved rigorously for every consistent formal system containing a certain amount of finitary number theory” [21, p. 71]. But what about influences in the opposite direction? Did Turing, in OCN, make use of concepts or techniques from Gödel’s 1931 incompleteness paper [19]?

哥德尔曾多次赞扬 OCN，并从根本上借鉴了图灵的思想。他强调，“由于 A. M. 图灵的工作，现在可以给出形式系统的一般概念的精确且无可置疑的充分定义”，结果，他说，不完备性“可以严格证明每个包含一定量有限数论的一致形式系统”[21，第 71 页]。但反方向的影响又如何呢？图灵在 OCN 中是否利用了哥德尔 1931 年关于不完备性论文中的概念或技术[19]？

At first blush, one might suspect not, since famously, Turing was a lone worker par excellence. He once told his Bletchley Park colleague Patrick Mahon that he took on Naval Enigma in 1939 “because no one else was doing anything about it and I could have it to myself” [37, p. 279]. Turing’s friend and colleague Peter Hilton described him as “so often going back to first principles for his inspiration” [30, p. 23]. Making a study of what others had written about a topic was not at all Turing’s habit. Yet there is a widespread assumption that Turing did indeed make extensive use of Gödel’s prior work. Judson Webb, for example, said in his influential book on mechanism that Turing (and Church) “only succeed because of having the basic discoveries of Gödel to guide them” [49, p. 26].

乍一看，人们可能不这么认为，因为众所周知，图灵是一位杰出的孤独工作者。他曾告诉他的布莱切利园同事Patrick Mahon，他在 1939 年接手海军恩尼格玛密码机的破解工作，“因为没有其他人在做这件事，我可以独自承担” [37，第 279 页]。图灵的朋友兼同事Peter Hilton形容他“经常回到第一原理来寻找灵感” [30，第 23 页]，研究别人对某个主题的论述根本不是图灵的习惯。然而，人们普遍认为，图灵大量利用了哥德尔先前的工作。例如，Judson Webb在他关于机械论的颇具影响力的著作中说，图灵（和丘奇）“之所以成功，是因为有哥德尔的基本发现指导他们” [49，第 26 页]。

Prima facie, this assumption is a very reasonable one. After all, by 1935, Gödel’s incompleteness paper was well known to mathematical logicians—including Turing’s mentor, Max Newman—and Turing cited and discussed the paper in OCN. Moreover, Turing was in effect picking up where Gödel had left off. David Hilbert, Gödel’s target, had emphasized the need for consistency, completeness, and decidability, and Gödel’s paper dealt explicitly with the first two of these, but not the third. (As is well known, Gödel showed that the system he called PM, for Principia Mathematica, was incomplete and could not prove its own consistency.) Turing took up the third issue, the decision problem. His treatment—like Gödel’s treatment of the first two issues—made central use of the technique of diagonalization and the idea of denoting syntactical items by means of numbers. Furthermore, Turing’s sequel to OCN [46], completed in the spring of 1938, took Gödel’s 1931 work as its point of departure. The first line of that paper refers to Gödel’s “well known theorem.” Turing explained, in his opening paragraph, that he was going to explore the idea that from “a system L of logic a more complete system L′ may be obtained”—by Gödelian methods—and then moved on immediately to a discussion of “Gödel representations” [46, pp. 161–162].

表面上看，这个假设非常合理。毕竟，到 1935 年，哥德尔的不完备性论文已为数理逻辑学家（包括图灵的导师Max Newman）所熟知，图灵在 OCN 上引用并讨论了这篇论文。此外，图灵实际上是在继续哥德尔未竟的事业。哥德尔的目标David Hilbert强调了一致性、完备性和可判定性的必要性，而哥德尔的论文明确讨论了前两个问题，但没有讨论第三个问题。（众所周知，哥德尔证明了他称之为 PM（数学原理）的系统是不完备的，无法证明其自身的一致性。）图灵讨论了第三个问题，即判定问题。他的处理——就像哥德尔处理前两个问题一样——主要使用了对角法技术和用数字表示句法项的思想。此外，图灵于 1938 年春完成的 OCN 续篇 [46] 以哥德尔 1931 年的工作为出发点。该论文的第一行提到了哥德尔的“著名定理”，图灵在开篇段落中解释说，他将探索这样一种想法，即通过哥德尔方法，“从逻辑系统 L 中可以得到更完整的系统 L′”，然后立即开始讨论“哥德尔表示”[46，第 161-162 页]。

Our aim, however, is to inject a note of caution into the literature, since despite the prima facie reasonableness of this assumption, there is in fact little evidence in its favor. Indeed, Turing may have encountered Gödel’s incompleteness paper only after formulating the central ideas and proofs of OCN.

然而，我们的目的是给文献注入一丝谨慎，因为尽管这个假设表面上合理，但实际上几乎没有证据支持它。事实上，图灵可能只是在阐述了 OCN 的核心思想和证明之后才遇到哥德尔的不完备性论文。

First, let’s take a closer look at what can be called the Standard Story, according to which central ideas in OCN were imported from Gödel’s work. Like all good stories, the Standard Story comes in a number of different versions. Jürgen Schmidhuber, for example, claims that in OCN, Turing “merely reformulated Gödel’s work in an elegant way” [43, p. 1638]. Others present less severe versions of the story, whereby one or another—or several—of the central techniques in OCN are said to have derived from Gödel’s 1931 paper.

首先，让我们仔细看看所谓的“标准故事”，根据该故事，OCN 的核心思想是从哥德尔的作品中引入的。像所有好故事一样，“标准故事”有许多不同的版本。例如，Jürgen Schmidhuber 声称，在 OCN 中，图灵“只是以一种优雅的方式重新表述了哥德尔的作品” [43，第 1638 页]。其他人则提出了不太严肃的故事版本，其中 OCN 中的一项或多项核心技术据说源自哥德尔 1931 年的论文。

The Standard Story

标准故事

The idea that Turing’s 1936 work was inspired and informed by Gödel’s is common among authors with a detailed knowledge of the relevant technical developments, including computer scientists and historians of computing. The Standard Story is simply taken for granted in two monographs devoted to OCN, Charles Petzold’s 2008 book [40] and Christopher Bernhardt’s 2016 book [4]. Petzold writes, “Turing was undoubtedly inspired by the approach Gödel took in his Incompleteness Theorem in converting every mathematical expression into a unique number” [40, p. 138]. Bernhardt writes, “The idea of converting algorithms into binary strings might seem fairly natural to us today, but in Turing’s day it was not. Turing got the idea of encoding his machines from the work of Kurt Gödel who, for his work on the incompleteness theorems, had encoded statements in mathematics into strings of numbers … Turing borrowed the concept and applied it to algorithms” [4, p. 88]. Biographer Andrew Hodges writes, “In 1936, Turing did follow Gödel’s 1931 revolution in logic. His first citation was to Gödel, and he described his mathematical argument as similar to Gödel’s” [33, p. 1639].

对相关技术发展有详细了解的作者（包括计算机科学家和计算历史学家）普遍认为，图灵 1936 年的工作受到了哥德尔的启发和影响。标准故事在两本专门介绍 OCN 的专著中被理所当然地视为理所当然，即 Charles Petzold 2008 年出版的书籍 [40] 和Christopher Bernhardt 2016 年出版的书籍 [4]。 Petzold写道：“图灵无疑受到了哥德尔在不完全性定理中将每个数学表达式转换成一个唯一数字的方法的启发”[40，第 138 页]。 Bernhardt写道：“将算法转换成二进制字符串的想法在今天看来可能相当自然，但在图灵时代却并非如此。图灵从库尔特·哥德尔的工作中获得了编码机器的想法，哥德尔在不完备定理方面的工作中，将数学陈述编码为数字串……图灵借用了这个概念并将其应用于算法” [4，第 88 页]。传记作家Andrew Hodges写道：“1936 年，图灵确实遵循了哥德尔 1931 年的逻辑革命。他第一次引用的是哥德尔，他将自己的数学论证描述为与哥德尔的相似” [33，第 1639 页]。

The Standard Story is also endorsed by historians of computing. Liesbeth De Mol asserts—without providing any evidence—that “Turing relied on Gödel’s insight that these kind of problems can be encoded as a problem about numbers” [16]. Edgar Daylight states that “Turing used Gödel numbering to uniquely identify each of his machines with integers, a key element in the construction of his universal machine” [15, p. 16]. To substantiate this claim, Daylight rests content with a reference to the lines by Petzold that were quoted above; but Petzold offers no evidence for his claim that Turing’s approach was “inspired” by Gödel’s. Furthermore, Daylight’s claim is in fact false. Recursion theory pioneer Stephen Kleene pointed out that “Turing uses a totally different method of numbering linguistic objects than Gödel—one perhaps more natural to a person who is steeped in machines” [35, p. 492]. Gödel numbering involves coding via exponentiation of primes [19, pp. 178–179], whereas Turing encoded a machine’s instruction table by means of a simple substitution code, employing a key assigning a numeral to each component of his “instruction tables” (e.g., the letter A is coded by 1, the semicolon by 7, and so forth).

标准故事也得到了计算机历史学家的认可。Liesbeth De Mol断言——没有提供任何证据——“图灵依赖于哥德尔的洞察力，即这类问题可以编码为数字问题”[16]。Edgar Daylight表示，“图灵使用哥德尔编号用整数唯一地标识他的每台机器，这是构建他的通用机器的关键要素”[15，第 16 页]。为了证实这一说法，Daylight满足于引用上面引用的Petzold的话；但Petzold没有提供任何证据来证明他的说法，即图灵的方法“受到”了哥德尔的启发。此外，Daylight的说法实际上是错误的。递归理论先驱Stephen Kleene指出，“图灵使用的语言对象编号方法与哥德尔完全不同——对于一个沉迷于机器的人来说，这种方法可能更自然”[35，第 492 页]。哥德尔编号涉及通过素数的幂运算进行编码[19，第 178-179 页]，而图灵通过简单的替换码对机器的指令表进行编码，使用一个键为其“指令表”的每个组件分配一个数字（例如，字母 A 用 1 编码，分号用 7 编码，等等）。

Other parts of the Standard Story concern Gödel’s influence on further central concepts in OCN. Mark Priestley claims that “Turing applied and generalized existing work in logic, particularly that of Gödel,” and he gives several alleged examples in which Gödel’s work was “transcribed and used,” including the use of substitution and recursion in what Turing called skeleton tables and m-functions, as well as “Gödel’s technique of arithmetization … in the definition of the universal machine” [41, pp. 87, 96, 98]. Teresa Numerico, discussing the origins of the stored-program concept, says the idea that “instructions can be stored in memory coded as numbers,” essential to Turing’s universal machine, “came directly from the arithmetization technique used in logic by Gödel” [39, p. 183]. William Aspray says that “without question,” Gödel’s incompleteness theorem “led” Turing to the idea of “encoding instructions as numbers” [2, p. 192]. Again no evidence is presented. Diagonalization, central to Turing’s proof of undecidability, is another illustration. Bernhardt says Turing “borrowed another argument from Gödel who, in turn, had borrowed it from Cantor” [4, p. 12]. Yet when discussing the diagonal argument in OCN [45, pp. 246–248]. Turing in fact referred not to Gödel but to Ernest Hobson’s 1921 book [31, The Theory of Functions of a Real Variable.

标准故事的其他部分涉及哥德尔对 OCN 中其他核心概念的影响。Mark Priestley 声称“图灵应用并推广了现有的逻辑工作，特别是哥德尔的工作”，并给出了几个所谓的“转录和使用”哥德尔工作的例子，包括图灵所谓的骨架表和 m 函数中的替换和递归的使用，以及“哥德尔的算术技术……在通用机器的定义中”[41，第 87、96、98 页]。Teresa Numerico 在讨论存储程序概念的起源时表示，“指令可以以数字的形式存储在内存中”这一想法对图灵的通用机器至关重要，“直接来自哥德尔在逻辑中使用的算术技术”[39，第 183 页]。William Aspray说，毫无疑问，哥德尔的不完备定理“使”图灵想到了“将指令编码为数字”的想法 [2，第 192 页]。同样没有提供任何证据。对角法是图灵证明不可判定性的核心，也是另一个例证。伯恩哈特说，图灵“从哥德尔那里借用了另一个论证，而哥德尔又从康托那里借用了它” [4，第 12 页]。然而，在讨论 OCN [45，第 246-248 页] 中的对角线论证时，图灵实际上没有提到哥德尔，而是提到了Ernest Hobson 1921 年出版的著作 [31，《The Theory of Functions of a Real Variable》。

As we shall explain, we do not see any evidence for the Standard Story, either in the historical record, in OCN itself, or in Turing’s other writings from the time. We believe the Standard Story should therefore be regarded with skepticism. Worse yet, the historical record presents some serious challenges to the Standard Story. We explain these challenges in what follows. But first, we briefly discuss Turing’s library borrowing records. These have only recently come to light, and they contain some relevant information.

正如我们将要解释的那样，我们没有看到任何支持标准故事的证据，无论是在历史记录中，还是在 OCN 本身中，还是在图灵当时的其他著作中。因此，我们认为应该对标准故事持怀疑态度。更糟糕的是，历史记录对标准故事提出了一些严峻的挑战。我们将在下文中解释这些挑战。但首先，我们简要讨论一下图灵的图书馆借阅记录。这些记录最近才被曝光，其中包含一些相关信息。

Turing’s Library Records

图灵的图书馆记录

In March 1935, Turing wrote to his mother Sara (Figure 3) that he had “just joined the Cambridge Philosophical Society” [52]. Always hopeful of unearthing unknown documents, we recently contacted the Society—and struck gold. Detailed records of Turing’s borrowings from the Society’s library emerged into the light of day. These provide fresh information about the timeframes of Turing’s various research projects and are a fascinating window on his mathematical interests, from the mid-1930s up to his final borrowing from the library, in July 1950.

1935 年 3 月，图灵写信给他的母亲Sara（图 3），说他“刚刚加入了剑桥哲学学会” [52]。我们一直希望发掘未知的文件，最近我们联系了学会，并一举成功。图灵从学会图书馆借阅的详细记录被公之于众。这些记录提供了有关图灵各种研究项目时间框架的新信息，也是了解他的数学兴趣的一个迷人窗口，从 20 世纪 30 年代中期到 1950 年 7 月他最后一次从图书馆借阅。

The Philosophical Society, founded in 1819, embraced not only natural philosophy narrowly construed (i.e., physics) but also “Chemistry, Mineralogy, Geology, Botany, Zoology, and other branches of Natural Science” and had many notable members over the years (including Charles Babbage, Niels Bohr, George Boole, Charles Darwin, Paul Dirac, Arthur Eddington, Godfrey Harold Hardy, and Ernest Rutherford). The Society elected Turing a Fellow at its meeting of February 25, 1935 (the great Rutherford delivered a lecture on radioactivity at the same meeting). Turing said he joined “principally because they have an excellent Mathematical & Scientific library” [52]. Situated along Pembroke Street, the library was close to King’s Parade, and a few minutes’ walk would take Turing from his rooms in King’s to one of the best collections of mathematical journals in Europe. The Society’s library held “the widest range of journals in Cambridge,” explains historian Susannah Gibson [18, p. 62]. By the 1920s, the library was taking approximately 300 scientific journals not found in the University Library [24, p. 68]. “[I]t was to the Society that people went when they wanted to read the most up-to-date research … The colleges and University could not compete [24, p. 68].

哲学学会成立于 1819 年，其研究范围不仅包括狭义的自然哲学（即物理学），还包括“化学、矿物学、地质学、植物学、动物学和其他自然科学分支” ，多年来拥有许多著名会员（包括Charles Babbage, Niels Bohr, George Boole, Charles Darwin, Paul Dirac, Arthur Eddington, Godfrey Harold Hardy, and Ernest Rutherford）。该学会在 1935 年 2 月 25 日的会议上选举图灵为会员（伟大的Rutherford在同一次会议上发表了关于放射性的演讲）。 图灵说他加入“主要是因为他们有一个优秀的数学和科学图书馆” [52]。图书馆位于Pembroke Street，靠近King’s Parade，从他在国王大道的房间步行几分钟就可以到达欧洲最好的数学期刊收藏地之一。历史学家Susannah Gibson解释说，该学会的图书馆收藏着“剑桥最广泛的期刊”[18，第 62 页]。到 20 世纪 20 年代，该图书馆收藏了约 300 种大学图书馆所没有的科学期刊 [24，第 68 页]。“当人们想阅读最新的研究成果时，他们就会去学会……学院和大学无法与之竞争 [24，第 68 页]。

Turing was able to borrow from the Society’s library from November 1934, probably on the strength of his fellowship proposal (Figure 4). His first recorded borrowing, on November 29, 1934—a month or so before the start of the Foundations of Mathematics lectures by Newman that are discussed below—was the July 1934 issue of the Transactions of the American Mathematical Society. This contained John von Neumann’s article “Almost Periodic Functions in a Group. I” [48], and Turing borrowed the 1934 Transactions again in January 1935. He saw a way of improving on von Neumann’s argument, and soon, toward the end of April, the manuscript of his first publication was ready for submission. It comprised a short proof that von Neumann’s twin concepts of left almost periodicity and right almost periodicity, which von Neumann had treated as being independent, were equivalent [44].

从 1934 年 11 月起，图灵得以从学会图书馆借阅，这或许得益于他的奖学金提案（图 4）。 有记录以来，他第一次借阅的是 1934 年 11 月 29 日的《美国数学学会会刊》，大约是在Newman下面要讨论的“数学基础”讲座开始前一个月。这期杂志刊登了John von Neumann的文章《群中的概周期函数。I》[48]。1935 年 1 月，图灵再次借阅了 1934 年的《美国数学学会会刊》。 他找到了改进John von Neumann论证的方法，很快，到 4 月底，他的第一份出版物的手稿就准备好提交了。它包含一个简短的证明，证明John von Neumann认为独立的左概周期和右概周期这两个孪生概念是等价的 [44]。

The library records show that on February 4, 1935, Turing borrowed the December 1930 volume of Mathematische Annalen, not returning it until March (having made one trip to the library to renew it, at the end of February). This volume contains David Hilbert’s “Probleme der Grundlegung der Mathematik” (Problems Concerning the Foundation of Mathematics), the text of an address he had delivered in Bologna in 1928 [27]. Here Hilbert famously stated that “in mathematics there is no ignorabimus, rather we are always able to answer meaningful questions,” and he described his “new foundation for mathematics, which can appropriately be called proof theory” [27, pp. 9, 3]. Hilbert mentioned the Entscheidungsproblem (decision problem), reporting [27, p. 8) that the decidability of the monadic predicate calculus—a special case of the Entscheidungsproblem—had been established in 1915 by Leopold Löwenheim [36] and “later in final form” by Hilbert’s protégé Heinrich Behmann [3].  Turing, of course, went on to show that “the Hilbert Entscheidungsproblem can have no solution” in the case of the full predicate calculus and all mathematical systems containing it [45, p. 259].

图书馆记录显示，1935 年 2 月 4 日，图灵借了 1930 年 12 月版的《数学年鉴》，直到 3 月才归还（2 月底，他曾去图书馆续借一次）。这一卷包含David Hilbert的《数学基础问题》（Probleme der Grundlegung der Mathematik），这是他 1928 年在 Bologna发表的演讲全文 [27]。Hilbert在这里有句名言：“数学中没有无知，相反，我们总是能够回答有意义的问题”，并描述了他的“数学新基础，可以恰当地称为证明理论” [27，第 9、3 页]。Hilbert提到了 Entscheidungsproblem（判定问题），报道 [27，第 133 页]) 一元谓词演算的可判定性（判定性问题的一个特例）由Leopold Löwenheim [36] 于 1915 年建立，Hilbert的门生Heinrich Behmann [3] 后来“以最终形式”确立。当然，图灵继续证明，在完整的谓词演算和所有包含它的数学系统中，“希尔伯特判定性问题不可能有解” [45，第 259 页]。

On April 18, 1936, Turing borrowed the December 1935 volume of Monatshefte für Mathematik und Physik, returning to the library to renew it on May 5 and then again on May 22. Strikingly, this volume contains a paper by Rudolf Carnap titled “Ein Gültigkeitskriterium für die Sätze der klassischen Mathematik” (A Criterion of Validity for the Propositions of Classical Mathematics). Carnap wrote:

1936 年 4 月 18 日，图灵借阅了 1935 年 12 月的《数学与物理月刊》，并于 5 月 5 日和 5 月 22 日再次到图书馆续借。引人注目的是，该卷包含 Rudolf Carnap的一篇论文，题为“Ein Gültigkeitskriterium für die Sätze der klassischen Mathematik”（古典数学命题的有效性标准）。 Carnap写道：

One can pose the problem of finding a definite criterion of validity, i.e., one whose satisfaction or non-satisfaction in any individual case could be decided in a finite number of steps by a fixed procedure … Were such a criterion found, we would have a decision procedure [Entscheidungsverfahren] for mathematics; we could then—so to speak—calculate the truth or falsity of every given proposition [6, p. 163, translated by Copeland and Sommaruga].

人们可以提出这样的问题：寻找一个明确的有效性标准，即，在任何个案中，该标准是满足还是不满足，可以通过一个固定的程序，在有限的步骤中来决定......如果找到了这样的标准，我们将有一个数学的决策程序[Entscheidungsverfahren]；然后，我们可以——可以这么说——计算出每个给定命题的真假[6，第 163 页，由 Copeland 和 Sommaruga 译]。

Assuming that Turing read these words, they must have held considerable interest. For Carnap was anticipating Turing’s hard-won, and at that stage unpublished, negative result—and, worse still, attributing it to Gödel. “Based on Gödel’s latest results,” Carnap said, “it appears hopeless to search for a definite criterion of validity for the entire system of mathematics,” adding, “However, the question of solving this so-called Entscheidungsproblem for certain classes of propositions remains important and fertile” [6, pp. 163–164].

假设图灵读到了这些话，他们一定对此很感兴趣。因为Carnap预料到了图灵来之不易的、当时尚未发表的负面结果——更糟糕的是，他将其归功于哥德尔。“根据哥德尔的最新成果，” Carnap说，“寻找整个数学体系的明确有效性标准似乎是无望的，”他补充道，“然而，解决某些类命题的所谓判定性问题仍然很重要，而且富有成果”[6，第 163-164 页]。

On the day he first borrowed the December 1935 Monatshefte (April 18, 1936), Turing also borrowed the 1931 volume of the journal, volume 38. This contained Gödel’s incompleteness paper, “On Formally Undecidable Propositions of Principia Mathematica and Related Systems I.” Figure 5 shows the library borrowing record with Turing’s signature. No previous borrowings of this volume are recorded against Turing’s name. We will evaluate the significance of this information later in the discussion. Might Turing not have read Gödel’s incompleteness paper until mid-April 1936? But first, let’s examine Turing’s earliest known presentation of his undecidability results.

在他第一次借阅 1935 年 12 月月刊（1936 年 4 月 18 日）的那天，图灵还借阅了该期刊 1931 年的第 38 卷。其中包含哥德尔的不完备性论文“论数学原理和相关系统 I 的形式不可判定命题”。图 5 显示了带有图灵签名的图书馆借阅记录，之前没有以图灵的名义记录过该卷的借阅记录，我们将在后面的讨论中评估此信息的重要性。图灵可能直到 1936 年 4 月中旬才读到哥德尔的不完备性论文吗？但首先，让我们来看看图灵最早对他的不可判定性结果的陈述。

Turing’s Précis of “On Computable Numbers”

图灵的《论可计算数》摘要

Turing’s précis is an important source of evidence concerning the development of OCN. Just over a page and a half in length, it is Turing’s earliest surviving account of the core ideas and arguments of OCN. Written in French, it is little known; advocates of the Standard Story never mention it. Small fragments have been translated in [11] and [12], but a full translation has not so far been published.

图灵的摘要是有关 OCN 发展的重要证据来源。它只有一页半多长，是图灵现存最早的关于 OCN 核心思想和论点的描述。它是用法语写的，鲜为人知；标准故事的倡导者从未提及它。[11] 和 [12] 中已经翻译了一些小片段，但完整的翻译至今尚未出版。

The typescript (Figure 6) survived among Sara Turing’s papers and is marked on the first page “Copy of first rough draft of précis of ‘Computable Numbers’ made for ‘Comptes Rendues’” [53]. Turing intended to publish it in Comptes rendus hebdomadaires des séances de l’Académie des Sciences. Turing and Sara evidently worked together on the draft; Sara wrote, “we embarked together on a précis in French of ‘Computable Numbers’ ” [47, p. 49]. It seems the précis was never published. Turing wrote to Sara on May 29, 1936, saying:

打字稿（图 6）在Sara Turing的论文中幸存了下来，第一页标有“为《计算数汇编》撰写的《可计算数》摘要第一​​稿的副本”[53]。图灵打算将其发表在《Comptes rendus hebdomadaires des séances de l’Académie des Sciences》上。图灵和萨拉显然是一起起草的；萨拉写道：“我们一起着手编写《可计算数》的法语摘要”[47，第 49 页]，但这份摘要似乎从未发表过，图灵于 1936 年 5 月 29 日写信给萨拉说：

The situation with regard to the note for Comptes Rendus was not so good. It appears that the man who I wrote to, and whom I asked to communicate the paper for me had gone to China, and moreover the letter seems to have been lost in the post … [55].

给 Comptes Rendus 的信函情况不太好。看来，我写信的那个人，我请他帮我转交文件的人已经去了中国，而且这封信似乎在邮寄中丢失了……[55]

Sara later summed matters up: “the war supervened and Alan, as far as I know, heard no more” [47, p. 49].

萨拉后来总结道：“战争爆发了，据我所知，艾伦再也没有听到任何消息”[47，第 49 页]。

The typescript is undated, but its approximate date is clear from a letter Turing wrote to Sara on May 4. He told her he had had the précis “vetted by a French expert” and had “sent it off” [54]. Probably the draft was written in the Cambridge Easter vacation (March 26–April 15) while Turing was staying at the family home in Guildford [54].

打字稿没有注明日期，但从图灵 5 月 4 日写给萨拉的一封信中可以清楚地看出它的大致日期。他告诉她，他已经让一位法国专家“审查了摘要”并“寄出去了”[54]。草稿可能是在剑桥复活节假期（3 月 26 日至 4 月 15 日）期间写的，当时图灵住在 Guildford的家中[54]。

In the same letter (May 4), Turing mentioned having sought Max Newman’s (Figure 7) opinion on the précis, saying that Newman “examined my note for C.R. and approved it after some alterations.” Newman, a Fellow of St John’s, had lectured the previous year on the Foundations of Mathematics, in the Cambridge Lent term of 1935. He presented Hilbert’s Entscheidungsproblem to his audience, and said 40 years later (in a tape-recorded interview) that Turing’s journey leading to OCN had “started because he attended a lecture of mine.”Footnote 11

在同一封信（5 月 4 日）中，图灵提到曾就摘要征求过Max Newman（图 7）的意见，并表示纽曼“审查了我为 C.R. 写的笔记，并在进行了一些修改后批准了它”。Newman是圣约翰大学的研究员，曾在前一年，即 1935 年剑桥大学四旬斋学期讲授过数学基础课程。他向听众介绍了希尔伯特的判定问题，并在 40 年后（在一次录音采访中）表示，图灵通往 OCN 的旅程“始于他听了我的讲座”。

Since the précis bears importantly on our topic, we translate it in full. One can call the numbers whose decimals can be written down by a machine “computable.” Such a machine has a tape, in some ways analogous to paper, running through it. The tape is divided into sections called “squares.” Each square can bear a symbol, but this is not necessary. The squares that bear no symbol are called “blank squares.” The machine is capable of several m-configurations, q1.........qn; i.e. levers, wheels, et cetera can be arranged in several ways, called “m-configurations.” At any moment only one square appears in the machine. This square is called “the viewed square,” the symbol on it is called “the viewed symbol.” “The viewed symbol” and the m-configuration together are called simply “the configuration.” The configuration determines the next motion of the machine which can go to the left or to the right, or write a new symbol on “the viewed square,” if it is empty, or erase “the viewed symbol.” Then it can change the m-configuration.

由于摘要与我们的主题密切相关，我们将其完整翻译。

- 人们可以将那些小数部分能够被机器写下来的数字称为“可计算的”。这种机器有一条磁带，在某些方面类似于纸，穿过它。磁带被分成几个部分，称为“方块”。每个方块可以带有一个符号，但这不是必须的。没有符号的方块称为“空白方块”。机器能够有多个 m 格局，q1.........qn；即杠杆、轮子等可以以多种方式排列，称为“m 格局”。任何时候机器中都只出现一个方块。这个方块称为“可见方块”，上面的符号称为“可见符号”。“可见符号”和 m格局一起简称为“格局”。格局决定了机器的下一个动作，可以向左或向右移动，或者在“可见方块”上写一个新符号（如果是空的），或者擦除“可见符号”。然后它可以改变m格局。

The symbols written by the machine include the figures of the number that it is computing and other symbols. The machine must never erase a figure.

- 机器写入的符号包括正在计算的数字和其他符号。机器绝不能擦除任何数字。

A veritable “computing machine” must write as many figures as one wants. Thus one calls a machine M “méchante” [literally “nasty” or “naughty”] if there is a number N such that M never writes N figures. A sequence of figures computed by a “non-méchante” machine is called a “computable sequence.” A number whose decimal expression is a computable sequence is called a “computable number.”

- 真正的“计算机”必须能够输出希望输出的任意多的数字。因此，如果存在一个数字 N，使得 M 永远不会输出 N 个数字，那么我们就称 M 为“méchante”[字面意思是“讨厌的”或“淘气的”]。由“non-méchante”机器计算的数字序列称为“可计算序列”。十进制表达式为可计算序列的数字称为“可计算数字”。

We show that the computable numbers comprise a quite broad yet enumerable class. It seems, on the contrary, that the application of Cantor’s diagonal process would demonstrate that this class cannot be enumerable. But the reasoning is fallacious. The correct application of the diagonal process shows there is no general process for deciding whether a machine is “méchante” or not. In other words, there is no machine which supplied with a description of any machine M decides whether M is “méchante.”

我们表明，可计算数包含一个相当广泛但可枚举的类别。相反，似乎应用康托尔的对角线过程会证明这个类别是不可枚举的。但这种推理是错误的。对角线过程的正确应用表明，没有通用的过程来决定一台机器是否是“méchante”。换句话说，没有一台机器在提供任何机器 M 的描述后就能决定 M 是否是“méchante”。

This theorem has many applications. This comes about as follows. It can be shown that there is no general process for deciding whether a machine M never writes the symbol 0. If “Machine M sometimes writes the symbol 0” is expressed in Hilbert’s calculus, a formula F(M) is obtained. If one had a solution of the Entscheidungsproblem one would have a general process for deciding whether F(M) is provable. That is to say a general process for deciding whether M ever writes 0. It has been shown that this is not possible. Therefore the Entscheidungsproblem has no solution.

- 这个定理有许多应用，其结果如下。可以证明，没有通用的过程来决定机器 M 是否从不写符号 0。如果用希尔伯特演算表示“机器 M 有时写符号 0”，则得到公式 F(M)。如果有一个Entscheidungsproblem的解，就会有一个通用的过程来决定 F(M) 是否可证明。也就是说，有一个通用的过程来决定 M 是否曾经写过 0。已经证明这是不可能的。因此Entscheidungsproblem没有解。

There is much of interest in the précis. First, there are small but intriguing variations in terminology between the précis and OCN. The delightfully mechanical “levers” and “wheels” of the précis do not occur in OCN, whereas the perfectly machine-like “scanned square” and “scanned symbol” of OCN do not occur in the précis. The awkward terms “circular machine” and “circle-free machine” of OCN had also apparently not yet been thought of, and “méchante” is used in the précis instead of “circular.” It is difficult to guess what English term the playful “méchante” translated, but perhaps “badly behaved” or even “wretched.”

摘要中有很多有趣的地方。首先，摘要和 OCN 之间的术语有细微但有趣的变化。摘要中令人愉悦的机械“杠杆”和“轮子”在 OCN 中没有出现，而 OCN 中完美机械的“扫描方块”和“扫描符号”在摘要中也没有出现。OCN 中尴尬的术语“circular machine”和“circle-free machine”显然也没有被想到，摘要中使用的是“méchante”，而不是“circular”。很难猜出这个爱开玩笑的“méchante”翻译的是什么英文词，但也许是“行为不端”甚至“可怜”。

Second, it is clear from the précis that the main ideas and fundamental structure of OCN were well established at the time of writing, including the definition of a computing machine and computable number, the diagonal argument, and the unsolvability of the Entscheidungsproblem. Of course, much of importance in OCN is necessarily omitted from the brief précis—including the reasons, amply spelled out in the published paper, for thinking that (what is now called) the Church–Turing thesis is true, the thesis that “the ‘computable’ numbers include all numbers which would naturally be regarded as computable” [45, p. 249]. Turing’s insouciant phrase “in other words” in the penultimate paragraph of the précis conceals some of the most important argumentation of OCN.

其次，从摘要中可以清楚地看出，OCN 的主要思想和基本结构在撰写本文时已经确立，包括计算机和可计算数的定义、对角线论证以及Entscheidungsproblem的不可解性。当然，OCN 中许多重要内容必然会从简短的摘要中省略，包括在发表的论文中充分阐述的认为（现在所谓的）丘奇-图灵论题是正确的理由，即“‘可计算’数包括所有自然被视为可计算的数”的论题 [45，第 249 页]。摘要倒数第二段中图灵漫不经心的短语“换句话说”掩盖了 OCN 的一些最重要的论证。

Third, the existence of the universal machine is not noted in the précis. This is perhaps unsurprising, since despite Turing’s detailed exposition of the universal machine in OCN, the machine figures only in a supplementary argument (in fact, one of the arguments hidden beneath that glib “in other words”).

第三，摘要中没有提到通用机器的存在。这也许并不奇怪，因为尽管图灵在 OCN 中详细阐述了通用机器，但该机器只出现在补充论证中（事实上，隐藏在那个油嘴滑舌的“换句话说”之下的论证之一）。

Fourth, and most importantly, Turing does not so much as mention Gödel. The précis contains no indication whatsoever that Turing was familiar with Gödel’s work. We will say more about this later

第四，也是最重要的一点，图灵根本没有提到哥德尔。摘要中没有任何迹象表明图灵熟悉哥德尔的工作。我们稍后会对此进行更多说明。

We next examine some important remarks by Church’s colleague Stephen Kleene, remarks that those who repeat the Standard Story seem to overlook.

接下来我们来研究一下丘奇的同事Stephen Kleene的一些重要言论，那些重复标准故事的人似乎忽略了这些言论。

Kleene’s Remarks

Kleene的评论

According to the Standard Story, Turing’s work was founded on, and was a development of, Gödel’s: Turing, it is said, “recast” Gödel’s findings “in the guise of the Halting Problem” [14, p. 133]. Kleene’s view of the matter was very different, however. Noting that “One sometimes encounters statements asserting that Gödel’s work laid the foundation for Church’s and Turing’s results,” Kleene went on: “It seems to me that the truth is that Church’s approach through λ-definability and Turing’s through his machine concept had quite independent roots (motivations), and would have led them to their main results even if Gödel’s paper [19] had not already appeared” [35, p. 491]. Then he said:

根据标准故事，图灵的工作建立在哥德尔的基础上，并且是哥德尔工作的发展：据说，图灵“以停机问题的名义” [14，第 133 页]“重塑”了哥德尔的发现。然而，Kleene对此事的看法截然不同，Kleene指出，“有时会遇到声称哥德尔的工作为丘奇和图灵的结果奠定了基础的说法”，他接着说：“在我看来，事实是，丘奇通过 λ 可定义性的方法和图灵通过机器概念的方法有着相当独立的根源（动机），即使哥德尔的论文 [19] 尚未发表，它们也会引导他们得出主要结果” [35，第 491 页]。然后他说：

Whether or not one judges that Church would have proceeded from his thesis to these [undecidability] results without his having been exposed to Gödel numbering, it seems clear that Turing in [“On Computable Numbers”] had his own train of thought, quite unalloyed by any input from Gödel. One is impressed by this in reading Turing [“On Computable Numbers”] in detail [35, pp. 491–492].

无论人们是否认为丘奇在没有接触过哥德尔编号的情况下会从他的论文得出这些[不可判定性]结果，很明显，图灵在[《论可计算数》]中有自己的思路，完全没有受到哥德尔的任何影响。在详细阅读图灵[《论可计算数》]时，人们对此印象深刻[35，第 491-492 页]。

These remarks—from someone who worked closely with Church and played a leading part in the development of computability theory in the 1930s—are not to be taken lightly. Moreover, Kleene’s claim that Turing’s thought was “unalloyed by any input from Gödel” certainly fits with what Turing said, and didn’t say, in his précis. At the time he wrote this summary of his ideas, Gödel’s work—if he even knew about it—did not merit a mention. In OCN, on the other hand, he gave a short, careful statement of the difference between his results and Gödel’s. That his findings were significantly different from Gödel’s could easily have been stated in the précis as well, for example using much the same words as in OCN: “It should perhaps be remarked that what I shall prove is quite different from the well-known results of Gödel” [45, p. 259]. But he did not do so.

这些评论——来自一位与丘奇密切合作并在 20 世纪 30 年代可计算性理论的发展中发挥了主导作用的人——不容小觑。此外，Kleene声称图灵的思想“没有受到哥德尔的任何影响”，这当然符合图灵在他的摘要中所说和未说的内容。在他写下他的想法摘要时，哥德尔的工作——如果他知道的话——并不值得一提。另一方面，在 OCN 中，他简短而谨慎地说明了他的结果与哥德尔的结果之间的差异。他的发现与哥德尔的发现有显著不同，这一点也可以在摘要中轻松说明，例如使用与 OCN 中相同的措辞：“也许应该指出，我将要证明的与哥德尔众所周知的结果完全不同”[45，第 259 页]。但他没有这样做。

We will take a close look at the text of OCN below. But first we introduce another relevant document, a letter by Cambridge don Richard Braithwaite (Figure 8) describing Turing’s knowledge of Gödel’s work at the time in question.

下面我们将仔细研究 OCN 的文本。但首先我们介绍另一份相关文件，即剑桥大学讲师Richard Braithwaite 的一封信（图 8），其中描述了图灵当时对哥德尔著作的了解。

Braithwaite on “Turing’s Complete Ignorance of Gödel’s Work”

Braithwaite 谈“图灵对哥德尔工作的完全无知”

According to the Standard Story, Turing learned about Gödel’s work on incompleteness during Max Newman’s 1935 lectures on the Foundations of Mathematics. Newman delivered the lectures on Tuesdays, Thursdays, and Saturdays during Lent term. Andrew Hodges says that “Newman’s lectures finished with the proof of Gödel’s theorem, and thus brought Alan up to the frontiers of knowledge” [32, p. 93]. Ivor Grattan-Guinness summarizes: “Turing, newly graduated from the tripos, sat in on [Newman’s] course in 1935 and learnt about decision problems and Gödel numbering from one of the few Britons who was familiar with them” [23, p. 439]. However, there is disagreement in the literature about this tidy picture of the transmission of ideas.

根据标准故事，图灵在 1935 年 Max Newman 的数学基础讲座中了解到了哥德尔关于不完备性的工作。Newman 在大斋期期间每周二、周四和周六进行讲座。Andrew Hodges 说：“Newman 的讲座以证明哥德尔定理结束，从而将 Alan 带到了知识的前沿”[32，第 93 页]。Ivor Grattan-Guinness 总结道：“图灵刚刚从三等学位毕业，于 1935 年旁听了 [Newman 的] 课程，并从少数熟悉决策问题和哥德尔编号的英国人那里了解了这些知识”[23，第 439 页]。然而，文献中对这种思想传播的清晰描述存在分歧。

Margaret Boden raised a difficulty for the idea that Turing’s knowledge of Gödel’s incompleteness theorems stemmed from Newman’s 1935 lectures, and indeed for the Standard Story in toto:

Margaret Boden对图灵关于哥德尔不完备定理的了解源自纽曼 1935 年的演讲这一观点提出了质疑，事实上对于整个标准故事而言也是如此：

One might expect that Turing’s first thoughts about computability would have been informed by Gödel’s theorem. But they weren’t. It’s not clear that he even knew about it when he wrote his paper in 1935. Certainly, Newman’s final lecture had mentioned it—but perhaps Turing hadn’t been there? There’s good evidence that he was introduced to Gödel’s work not by Newman, but by the philosopher Richard Braithwaite [5, p. 174].

人们可能以为，图灵对可计算性的最初想法是受到哥德尔定理的影响。但事实并非如此。尚不清楚他在 1935 年撰写论文时是否知道这一点。当然，纽曼的最后一场演讲提到了这一点——但也许图灵当时不在场？有充分的证据表明，图灵不是通过纽曼接触到哥德尔的作品，而是由哲学家 Richard Braithwaite [5，第 174 页] 介绍给他的。

Although Boden seems to indicate otherwise, the exact content of the 1935 lectures is in fact somewhat uncertain. But detailed notes were taken during Newman’s 1934 Foundations of Mathematics lectures, by his student Frank Smithies, later a distinguished mathematician, and these provide much valuable information about the lecture content in 1934 [51].

尽管 Boden 似乎另有所指，但 1935 年讲座的具体内容实际上有些不确定。但 Newman 的学生 Frank Smithies（后来成为杰出的数学家）在 1934 年的数学基础讲座上做了详细的笔记，这些笔记为 1934 年的讲座内容提供了许多有价值的信息 [51]。

There were nineteen lectures in total in 1934. Lecture 16 began with a discussion of the problem of proving the consistency of the Peano axioms and moved on to a presentation of the Entscheidungsproblem. Newman explained that the Entscheidungsproblem had been settled for the monadic predicate calculus. Then at the end of lecture 16 came a wide-ranging list of references: Russell and Whitehead’s Principia Mathematica, Russell’s Introduction to Mathematical Philosophy, Ramsey’s Foundations of Mathematics, Wittgenstein’s Tractatus Logico-Philosophicus, Hilbert and Bernays’s Grundlagen der Mathematik, papers by Hilbert, Brouwer, and Church, and also Gödel’s 1931 paper in the Monatshefte, which was to be the topic of the next three lectures (lectures 17–19).

1934 年总共有 19 场讲座。第 16 场讲座首先讨论了证明皮亚诺公理一致性的问题，然后介绍了判定性问题。纽曼解释说，判定性问题已为单子谓词演算解决了。然后，在第 16 讲结束时，出现了广泛的参考文献列表：罗素和怀特海的《数学原理》、罗素的《数学哲学导论》、拉姆齐的《数学基础》、维特根斯坦的《逻辑哲学论》、希尔伯特和伯内斯的《数学基本原理》、希尔伯特、布劳威尔和丘奇的论文，以及哥德尔 1931 年在《月刊》上发表的论文，该论文将成为接下来三讲（第 17-19 讲）的主题。

To judge from scattered references elsewhere in Smithies’s notes, Newman seems to have been using the 1934 Hilbert and Bernays Grundlagen der Mathematik [29] as a textbook, along with Hilbert and Ackermann’s 1928 Grundzüge der Theoretischen Logik [28]. If so, Newman’s lectures 17–19 ran well ahead of his 1934 textbook. Hilbert and Bernays did refer to Gödel’s 1931 paper (mentioning in particular his Proposition VII, that every primitive recursive relation is arithmetical), but only in connection with their sustained argument that primitive recursive definitions, and some more complicated recursive definitions, can be reduced to explicit definitions [29, p. 415, Footnote 1]. There was no mention of Gödel’s incompleteness theorems. The closest the book came to discussing these was the following remark by Hilbert, in his brief foreword to the book:

从Smithies笔记中其他地方的零散引用来看，纽曼似乎一直在使用 1934 年的希尔伯特和伯内斯的《数学原理》[29] 作为教科书，以及希尔伯特和阿克曼 1928 年的《理论逻辑原理》[28]。如果是这样的话，纽曼的 17-19 讲课远远领先于他 1934 年的教科书。希尔伯特和伯内斯确实提到了哥德尔 1931 年的论文（特别是提到他的命题 VII，即每个原始递归关系都是算术的），但仅限于他们持续的论证，即原始递归定义和一些更复杂的递归定义可以归结为明确的定义 [29，第 415 页，脚注 1]。没有提到哥德尔的不完备定理。本书最接近讨论这些问题的是希尔伯特在本书的简短序言中所做的以下评论：

I want to emphasize that the opinion, which has arisen from time to time, that the unfeasibility of my proof theory follows from certain recent results of Gödel’s, has been established to be erroneous. In point of fact, that result shows only that for more far-reaching consistency proofs, one must exploit the finitist standpoint in a sharper way than is necessary in the consideration of elementary formalisms [29, p. v; translated by Copeland and Sommaruga].

我想强调的是，人们时常认为我的证明理论不可行，这是哥德尔最近某些结果的必然结果，这种观点已被证实是错误的。事实上，这一结果仅表明，对于更深远的一致性证明，人们必须以比考虑基本形式主义时更敏锐的方式利用有限主义观点 [29，第 v 页；由 Copeland 和 Sommaruga 翻译]。

Smithies’s notes are our best (and only) evidence regarding the content of the 1935 lectures. In his lectures 17–19, during the final week of the 1934 course, Newman gave a tour of the central ideas of Gödel’s 1931 paper. He covered Gödel numbering, the construction of Gödel’s xBy (x is a proof of y) and Bew(x) (x is provable), Gödel’s Proposition V (every recursive relation is definable), and the concept of ω-consistency, followed by deliciously brief proofs of the first and second incompleteness theorems. Did Newman end his lectures in the same way in 1935? It is conjecture to say so, since no syllabus or notes seem to have survived, and there was no examination question relating to Gödel’s theorems in the 1935 Tripos. Nevertheless, in the absence of any evidence to the contrary, it seems not unreasonable to assume that Newman would have covered much the same material in the 1934 and 1935 versions of the course.

Smithies的笔记是我们关于 1935 年讲座内容的最好（也是唯一）证据。在 1934 年课程的最后一周，纽曼在第 17-19 讲中介绍了哥德尔 1931 年论文的核心思想。他讲解了哥德尔编号、哥德尔 xBy（x 是 y 的证明）和 Bew(x)（x 是可证明的）的构造、哥德尔命题 V（每个递归关系都是可定义的）和 ω 一致性的概念，随后是对第一和第二不完全性定理的简短证明。纽曼在 1935 年是否以同样的方式结束了他的讲座？只能推测，因为似乎没有教学大纲或笔记留存下来，而且 1935 年的 Tripos 考试中没有与哥德尔定理相关的考试问题。尽管如此，在没有任何相反证据的情况下，假设纽曼在 1934 年和 1935 年版本的课程中涵盖了相同的内容，这似乎并非不合理。

Boden questions whether Turing attended the final lectures of the course. Perhaps that week found him fully engrossed in completing what King’s mathematician Philip Hall (quoted in [47, p. 45) described as a “very pretty little proof,” submitted a few weeks later as “Equivalence of Left and Right Almost Periodicity.” Boden is right that whether Turing attended all the lectures is a matter for conjecture. (Newman reported only that Turing “attended a lecture of mine.”) On the other hand, Turing might indeed have attended every lecture and heard Newman give much the same introduction to Gödel’s results as he gave in 1934. To be clear, we believe there is no evidence either way, and the facts of the matter may by this time be unknowable.

Boden质疑图灵是否参加了课程的最后几堂课。也许那一周他全神贯注于完成国王学院数学家 Philip Hall（引自 [47，第 45 页）所描述的“非常漂亮的小证明”，几周后提交的论文名为“左和右几乎周期性的等价性”。Boden说得对，图灵是否参加了所有的讲座，这只能推测。（纽曼只说图灵“参加了我的一次讲座”。）另一方面，图灵可能确实参加了每一场讲座，并听到纽曼对哥德尔结果的介绍与他在 1934 年所做的介绍大致相同。需要明确的是，我们认为没有任何证据可以证明这一点，而且到现在为止，事情的真相可能已经无法知晓。

Turning to Boden’s claim that it was not Newman but Braithwaite who introduced Turing to Gödel’s work, her “good evidence” is a letter Braithwaite wrote to her in 1982. A Fellow of King’s from 1924, Braithwaite was a mathematically and scientifically oriented philosopher, working in the broadly logical positivist tradition, and he was involved in Turing’s election to a King’s junior research fellowship in March 1935. Braithwaite authored the 32-page introduction to the English translation of Gödel’s 1931 incompleteness paper [20], and he was intimately familiar with the pioneering work done on the Entscheidungsproblem by his close friend Frank Ramsey, also a Fellow of King’s. In 1928, in a paper Braithwaite edited for his 1931 posthumous collection of Ramsey’s papers, Ramsey described the Entscheidungsproblem as “one of the leading problems of mathematical logic,” and he solved it for important special cases [42].

对于Boden的说法，即不是Newman而是Braithwaite 将哥德尔的工作介绍给图灵，她的“有力证据”是布雷斯韦特在 1982 年写给她的一封信。Braithwaite 自 1924 年起成为国王学院的研究员，他是一位数学和科学导向的哲学家，遵循广义的逻辑实证主义传统。1935 年 3 月，他参与了图灵当选国王学院初级研究员的工作。Braithwaite 为哥德尔 1931 年不完备性论文 [20] 的英译本撰写了 32 页的序言，并且他非常熟悉他的密友Frank Ramsey在判定性问题上所做的开创性工作，拉姆齐也是国王学院的研究员。 1928 年，Braithwaite 在编辑的一篇论文中收录了Ramsey 1931 年遗著的论文集，Ramsey在论文中将Entscheidungsproblem 描述为“数理逻辑的主要问题之一”，并在一些重要的特殊情况下解决了该问题 [42]。

In his letter to Boden, Braithwaite remarked on “Turing’s complete ignorance of Gödel’s work when he wrote his ‘Computable Numbers’ paper.” Braithwaite continued: “I consider I played some part in drawing Turing’s attention to the relation of his work to Gödel’s.” Braithwaite’s recollection (if accurate) clearly undermines the Standard Story. However, contrary to Boden’s view (quoted above), it may not have been Braithwaite alone who was responsible for drawing Turing’s attention to the relation of his work to Gödel’s. Newman may have played a key role too (although more than a year later than the Standard Story relates), as we will explain.

在写给Boden的信中， Braithwaite评论道：“图灵在撰写《可计算数》论文时对哥德尔的工作一无所知。” Braithwaite继续说道：“我认为我在让图灵注意到他的工作与哥德尔的工作之间的关系方面发挥了一定作用。” Braithwaite的回忆（如果准确的话）显然破坏了标准故事。然而，与Boden的观点（上面引用）相反，让图灵注意到他的工作与哥德尔的工作之间的关系可能并不是Braithwaite一个人的责任。纽曼可能也发挥了关键作用（尽管比标准故事所说的晚了一年多），我们将解释这一点。

The Alternative Picture

另类图景

Not only is the précis the earliest surviving exposition of the central ideas of OCN, it seems it was also Newman’s entrée to Turing’s work on the topic. Turing wrote to Sara on May 4, 1936:

摘要不仅是现存最早的 OCN 核心思想阐述，而且似乎也是纽曼了解图灵关于该主题的研究的入门资料。图灵于 1936 年 5 月 4 日写信给萨拉：

I saw Mr Newman four or five days after I came up. He is very busy with other things just at present and says he will not be able to give his whole attention to my theory for some week or so yet. However he examined my note for C.R and approved it after some alterations [54].

我来后四五天见到了纽曼先生。他目前忙于其他事情，说他一周左右还不能全神贯注于我的理论。不过，他检查了我给 C.R 的笔记，并在做了一些修改后批准了它 [54]。

Concerning OCN itself, Turing said in the same letter, “I don’t think the full text will be ready for a fortnight or more yet.”

关于 OCN 本身，图灵在同一封信中说：“我认为全文还要两周或更长时间才能准备好。”

The approximate date of Turing’s meeting with Newman can be deduced. As previously mentioned, Turing had spent Easter at the family home in Guildford [54]. That year, Easter Sunday fell on April 12, and the new Cambridge term began on Thursday, April 16. If Turing “came up” on the Monday or Tuesday (and in the UK, traveling back home from Easter family gatherings on Easter Monday is often the norm), then his meeting with Newman was most likely on the 17th or 18th.

图灵与纽曼会面的大致日期可以推断出来。如前所述，图灵在吉尔福德的家中度过了复活节 [54]。那一年，复活节星期日是 4 月 12 日，剑桥新学期从 4 月 16 日星期四开始。如果图灵在星期一或星期二“出现”（在英国，复活节星期一从复活节家庭聚会回家通常是常态），那么他与纽曼的会面最有可能是在 17 日或 18 日。

Newman may have been surprised by the précis (to say the least). He did not then know of Church’s contemporaneous proof of unsolvability, and Turing had not previously said much about his own research. A few weeks later, Newman wrote that “Turing’s work is entirely independent: he has been working without any supervision or criticism from anyone” [50]. As he read through the précis, might Newman have quizzed Turing about the conspicuous absence of any mention of Gödel’s work? At any rate, on the 18th, Turing went to the Philosophical Society Library and borrowed the volume of Monatshefte containing Gödel’s 1931 paper. He kept it until June (Figure 5), while finalizing OCN for submission to the London Mathematical Society, where his typescript was received on May 28.

纽曼可能对这份摘要感到惊讶（至少可以这么说）。他当时并不知道丘奇同时证明的无解性，而图灵此前也没有过多谈论自己的研究。几周后，纽曼写道：“图灵的工作完全是独立的：他一直在没有任何监督或批评的情况下工作”[50]。当他阅读这份摘要时，纽曼可能会问图灵为什么其中明显没有提到哥德尔的工作？无论如何，18 日，图灵去了哲学学会图书馆，借了包含哥德尔 1931 年论文的《月刊》。他一直把它留到 6 月（图 5），同时将 OCN 提交给伦敦数学学会，他的打字稿于 5 月 28 日收到。

As we noted earlier, Turing had not previously borrowed the 1931 volume, according to the library records. Might he have obtained it on prior occasions from another source, or perhaps read it in the Philosophical Society Library without borrowing it? This certainly cannot be ruled out. Turing’s own college library did not take the Monatshefte, and there were no copies elsewhere in the Cambridge library system apart from the University Library. This was more than twice as far from King’s as the Philosophical Society Library, which Turing could walk to from his rooms in three minutes or less. He might have borrowed the 1931 Monatshefte from the University Library, though he was, as we have seen, in the habit of borrowing the journals he needed from the Philosophical Society Library. Later, once an offprint of Church’s Entscheidungsproblem paper had arrived in Cambridge—an event Newman described as “painful” for Turing [50]—some modifications to OCN were necessary. Turing added a short appendix “Computability and Effective Calculability,” dated August 28, 1936. His only reference in the appendix was to a paper by Church’s student Kleene, in the 1935 volume of the American Journal of Mathematics. Once again, Turing used the Philosophical Society Library, borrowing the 1935 volume of the journal on August 15, 1936.

正如我们之前所指出的，根据图书馆记录，图灵之前没有借过 1931 年的那卷。他可能之前从其他来源获得过它，或者可能在哲学学会图书馆读过它而没有借阅？当然不能排除这种可能性。图灵自己的大学图书馆没有收藏《月刊》，除了大学图书馆外，剑桥图书馆系统其他地方也没有副本。这里离国王学院的距离是哲学学会图书馆的两倍多，图灵从他的房间步行到哲学学会图书馆只需三分钟或更短的时间。他可能从大学图书馆借了 1931 年的《月刊》，尽管正如我们所见，他习惯从哲学学会图书馆借阅他需要的期刊。后来，当丘奇的判定问题论文的单行本抵达剑桥时——纽曼将此描述为图灵的“痛苦”[50]——OCN 的一些修改是必要的。图灵添加了一个简短的附录“可计算性和有效可计算性”，日期为 1936 年 8 月 28 日。附录中他唯一引用的是丘奇的学生克莱尼在 1935 年《美国数学杂志》上发表的一篇论文。图灵再次使用了哲学学会图书馆，于 1936 年 8 月 15 日借阅了 1935 年的期刊。

Braithwaite’s letter, in conjunction with Kleene’s remarks discussed above, and the fact that the March or early April 1936 précis did not mention Gödel, make an alternative proposition worthy of consideration, namely that Turing first came to appreciate “the relation of his work to Gödel’s” (Braithwaite’s phrase) in approximately mid-April 1936, and by then, of course, OCN was virtually complete. Turing’s thinking on how best to present his results does seem to have changed markedly over a period of a few weeks. In the précis, he saw no need to refer to Gödel, whereas OCN contains brief but deep remarks on Gödel’s work (these remarks are examined in the next section).

Braithwaite的信，加上Kleene的上述评论，以及 1936 年 3 月或 4 月初的摘要中没有提到哥德尔的事实，提出了一个值得考虑的替代命题，即图灵第一次意识到“他的工作与哥德尔的工作之间的关系”（Braithwaite的说法）是在 1936 年 4 月中旬左右，当然，到那时，OCN 已经基本完成。在几周的时间里，图灵对如何最好地展示他的成果的想法似乎发生了显著的变化。在摘要中，他认为没有必要提到哥德尔，而 OCN 包含对哥德尔工作的简短而深刻的评论（这些评论将在下一节中讨论）。

This alternative proposition allows that Turing may already have had some prior knowledge of Gödel’s work, from attending Newman’s lectures. Braithwaite’s phrase “complete ignorance” (our italics) may have been emphatic rather than literal. Braithwaite’s essential point seems to be that, as he said, he “played some part in drawing Turing’s attention to the relation of his work to Gödel’s” (our italics).

这一替代命题允许图灵通过参加纽曼的讲座预先了解哥德尔的工作。Braithwaite的短语“完全无知”（我们的斜体）可能是强调性的，而不是字面意义上的。Braithwaite的要点似乎是，正如他所说，他“在引起图灵注意他的工作与哥德尔的工作之间的关系方面发挥了一定作用”（我们的斜体）。

While the considerations we have set out so far in the discussion are suggestive, we certainly do not mean to be understood as claiming that this alternative proposition is correct. We keep an open mind. The presently available evidence is visibly insufficient for such a claim. Our point is rather that given the available evidence, this alternative proposition is no less probable than the Standard Story, and indeed sits rather more comfortably with the known and reported facts (as we shall continue to argue in the next section). Our aim is simply to show that the Standard Story transcends the evidence and is highly speculative.

虽然我们在讨论中迄今为止提出的考虑具有启发性，但我们当然不想被理解为声称这个替代命题是正确的。我们保持开放态度。目前可用的证据显然不足以支持这种说法。我们的观点是，鉴于现有证据，这个替代命题的可能性并不低于标准故事，而且确实与已知和报道的事实更加吻合（我们将在下一节继续论证）。我们的目的只是表明标准故事超越了证据，并且具有高度的推测性。

Let us indulge in some speculation of our own. When Turing consulted Newman about the précis in April 1936, it seems not unlikely that Newman would have advised him to familiarize himself with the relation of his work to Gödel’s. Furthermore, it is probable that soon after returning to Cambridge from the Easter vacation, Turing met not only Newman but also Braithwaite (since Braithwaite and Turing were both Fellows of King’s). If Turing sought Braithwaite’s opinion on the précis—and why would he not have consulted an expert on the Entscheidungsproblem from his own college?—then to judge by Braithwaite’s letter, he would have received the same advice, to familiarize himself with the relation of his work to Gödel’s. Thus, Turing’s visit to the Philosophical Society Library on April 18 may have been precipitated by both Braithwaite and Newman. Indeed, Newman showed no great interest in Carnap, whereas Braithwaite had a keen interest (his 1930s papers contain discussions of Carnap’s ideas, and his 1953 opus major Scientific Explanation was strongly influenced by Carnap’s view of scientific theories as interpreted deductive calculi).

让我们来做些自己的推测。1936 年 4 月，当图灵向纽曼咨询摘要时，纽曼似乎不太可能建议他熟悉他的工作与哥德尔的工作之间的关系。此外，图灵在复活节假期返回剑桥后不久，很可能不仅遇到了纽曼，还遇到了布雷斯韦特（因为Braithwaite和图灵都是国王学院的研究员）。如果图灵征求Braithwaite对摘要的意见——他为什么不咨询自己学院的判定问题专家呢？——那么从Braithwaite的信来看，他会得到同样的建议，熟悉他的工作与哥德尔的工作之间的关系。因此，图灵 4 月 18 日访问哲学学会图书馆可能是由Braithwaite和纽曼促成的。事实上，纽曼对Carnap并没有表现出太大的兴趣，而Braithwaite却兴趣浓厚（他在 1930 年代的论文中讨论了Carnap的思想，而他 1953 年的主要著作《科学解释》深受Carnap将科学理论视为解释演绎演算的观点的影响）。

The Text of “On Computable Numbers”

《论可计算数》文本

As is well known, OCN referred to Gödel’s 1931 article. In this section, we examine each mention of Gödel in Turing’s text.

众所周知，OCN 引用了哥德尔 1931 年的文章。在本节中，我们将研究图灵文本中对哥德尔的每一次提及。

When Turing turned to modifying his draft in order to take account of Church’s 1936 publications [7, 8, he added merely two sentences to the text [45, p. 231]: “In a recent paper Alonzo Church has introduced an idea of ‘effective calculability,’ which is equivalent to my ‘computability,’ but is very differently defined. Church also reaches similar conclusions about the Entscheidungsproblem.” Turing dealt with Gödel’s 1931 article in a similar fashion. His text includes no more than three short mentions of Gödel.

当图灵为了将丘奇 1936 年的出版物 [7, 8] 纳入考虑范围而修改草稿时，他只在文本 [45，第 231 页] 中添加了两句话：“在最近的一篇论文中，阿隆佐·丘奇引入了‘有效可计算性’的概念，它等同于我的‘可计算性’，但定义截然不同。丘奇还对判定性问题得出了类似的结论。”图灵以类似的方式处理了哥德尔 1931 年的文章。他的文本中对哥德尔的提及不超过三次。

The first mention is at the foot of the first page, immediately before Turing’s brief remark about Church. He said simply, “By the correct application of one of these arguments, conclusions are reached which are superficially similar to those of Gödel” [45, p. 230]. The second mention does not come until more than halfway through the paper and is no more than a passing remark in parentheses [45, p. 248]. To the sentence “For each of these ‘general process’ problems can be expressed as a problem concerning a general process for determining whether a given integer n has a property G(n), and this is equivalent to computing a number whose n-th figure is 1 if G(n) is true and 0 if it is false,” Turing added a parenthesis, immediately following the first occurrence of G(n):

第一次提到是在第一页的底部，就在图灵对丘奇的简短评论之前。他只是说，“通过正确应用这些论证之一，可以得出与哥德尔论证表面上相似的结论”[45，第 230 页]。第二次提到它直到论文的一半以上才出现，而且只不过是括号中的一句顺便评论[45，第 248 页]。对于这句话“对于这些‘一般过程’中的每一个，问题都可以表示为一个有关确定给定整数 n 是否具有属性 G(n) 的一般过程的问题，这等同于计算一个数字，如果 G(n) 为真，则第 n 位为 1，如果为假，则第 n 位为 0”，图灵在第一次出现 G(n) 之后立即添加了一个括号：

[e.g. G(n) might mean “n is satisfactory” or “n is the Gödel representation of a provable formula”].

[例如 G(n) 可能表示“n 令人满意”或“n 是可证明公式的哥德尔表示”]。

His inconsistent use of square brackets was probably a result of lack of care as he made the insertion; elsewhere in the paper he always used round brackets for within-sentence parentheses (including parentheses of the same length as the above).

他不一致地使用方括号可能是由于他在插入时缺乏细心；在论文的其他地方，他总是使用圆括号表示句内括号（包括与上述长度相同的括号）。

The third and last mention of Gödel comes almost right at the end of the paper, in the final section, “Application to the Entscheidungsproblem” [45, p. 259]. Turing’s principal aim in mentioning Gödel at that point was evidently (as with the mention on the first page) to distance his work from Gödel’s. He said succinctly:

第三次也是最后一次提到哥德尔是在论文的最后，即最后一节“应用于判定问题”[45，第 259 页]。图灵在此时提到哥德尔的主要目的显然是（与第一页的提及一样）将他的工作与哥德尔的工作区分开来。他简洁地说：

It should perhaps be remarked that what I shall prove is quite different from the well-known results of Gödel. Gödel has shown that (in the formalism of Principia Mathematica) there are propositions such that neither nor – is provable. As a consequence of this, it is shown that no proof of consistency of Principia Mathematica (or of K) can be given within that formalism. On the other hand, I shall show that there is no general method which tells whether a given formula is provable in K, or, what comes to the same, whether the system consisting of K with – adjoined as an extra axiom is consistent [45, p. 259].

也许应该指出，我将要证明的内容与哥德尔的著名结果截然不同。哥德尔已经证明（在《数学原理》的形式体系中），存在这样的命题，既不能证明也不能证明 –。由此可知，在该形式体系中无法给出《数学原理》（或 K）一致性的证明。另一方面，我将证明，没有通用方法可以说明给定公式在 K 中是否可以证明，或者，同样，由 K 和作为额外公理附加的 – 组成的系统是否一致 [45，第 259 页]。

Then, in the next sentence, Turing noted:

然后，在下一个句子中，图灵指出：

If the negation of what Gödel has shown had been proved, i.e. if, for each , either or – is provable, then we should have an immediate solution of the Entscheidungsproblem. For we can invent a machine which will prove consecutively all provable formulae [45, p. 259].

如果哥德尔所展示的否定已经被证明，即，如果对于每个 ， 或 – 都是可证明的，那么我们应该立即得到判定问题的解。因为我们可以发明一种机器，它可以连续证明所有可证明的公式 [45，第 259 页]。

Turing’s point here—plainly if modestly expressed—is that Gödel’s first incompleteness result follows immediately from his own quite different undecidability result. This was the first mention of a road gratefully followed by many a logician and computer scientist since. Gödel’s first incompleteness theorem can be regarded as an immediate corollary of (what Scott Aaronson calls) Turing’s conceptually prior undecidability theorem [1]—and with no need to mention Gödel numbers or the labyrinth of subsidiary definitions involved in defining Gödel’s Bew(x).

图灵在这里的观点——虽然表达得比较谦虚——是，哥德尔的第一个不完备性结果直接源于他自己完全不同的不可判定性结果。这是第一次提到一条自那以后许多逻辑学家和计算机科学家都欣然遵循的道路。哥德尔的第一个不完备性定理可以看作是图灵概念上先验的不可判定性定理 [1]（斯科特·阿伦森称之为）的直接推论——无需提及哥德尔数或定义哥德尔的 Bew(x) 所涉及的大量辅助定义。

There is, then, no evidence for the Standard Story to be found in Turing’s references to Gödel’s work in OCN. The text of OCN contains nothing at all to indicate that Gödel’s work was the foundation for Turing’s, or that Turing used concepts or techniques drawn from Gödel’s 1931 paper. On the contrary, Turing’s brief remarks concerning Gödel served only to emphasize—firmly—that his own work was very different. The text of OCN itself provides the greatest challenge to the Standard Story, as Kleene observed.

因此，图灵在 OCN 中对哥德尔工作的引用中没有找到任何证据来证明标准故事。OCN 的文本中根本没有任何内容表明哥德尔的工作是图灵工作的基础，或者图灵使用了从哥德尔 1931 年的论文中汲取的概念或技术。相反，图灵对哥德尔的简短评论只是强调——坚定地——他自己的工作非常不同。正如克莱尼所观察到的，OCN 文本本身对标准故事提出了最大的挑战。

Concluding Remarks

结束语

We have assembled an array of challenges to the Standard Story, and we have developed a plausible alternative picture that sits more comfortably with the record. Both accounts are short on decisive evidence. We conclude that no one should claim that central ideas in OCN were imported from Gödel’s work unless both the existence of a conflicting account and a lack of deciding evidence is acknowledged.

我们收集了一系列对标准故事的挑战，并提出了一个更符合记录的合理替代图景。这两种说法都缺乏决定性的证据。我们得出的结论是，除非承认存在相互矛盾的说法和缺乏决定性证据，否则任何人都不应该声称 OCN 的核心思想是从哥德尔的作品中引进的。

It is one of the great ironies of the history of logic that all along, incompleteness sufficed to establish undecidability. This was first noted more than thirty years after Gödel’s paper appeared, by Martin Davis [13, p. 109], [34, p. 136]. Naturally, this does not diminish Turing’s, nor Church’s, great achievement. Back in the day, Carnap and others suspected the existence of an implication from Gödel’s results to a negative solution of the Entscheidungsproblem, but no proof existed. In 1931, commenting on Gödel’s recently published incompleteness results, Herbrand said cautiously, “[A]lthough at present it seems unlikely that the decision problem can be solved, it has not yet been proved that it is impossible to do so” [26, p. 259]. Newman later summed up matters as they had appeared at the time, before Turing and Church produced their transformational proofs:

逻辑史上最大的讽刺之一就是，不完备性就足以建立不可判定性。 Martin Davis [13，第 109 页]、[34，第 136 页] 在哥德尔的论文发表 30 多年后首次指出了这一点。当然，这并没有贬低图灵或丘奇的伟大成就。当时，卡尔纳普和其他人怀疑哥德尔的结果蕴含着判定问题的否定解，但没有证据。1931 年， Herbrand 在评论哥德尔最近发表的不完备性结果时谨慎地说道：“尽管目前看来判定问题不太可能得到解决，但尚未证明它不可能得到解决” [26，第 259 页]。纽曼后来总结了当时在图灵和丘奇提出变换证明之前出现的问题：

A first blow was dealt [to the Hilbert program] by Gödel’s incompleteness theorem (1931), which made it clear that truth or falsehood of A could not be equated to provability of A or not-A in any finitely based logic, chosen once for all; but there still remained in principle the possibility of finding a mechanical process for deciding whether A, or not-A, or neither, was formally provable in a given system [38, p. 256].

哥德尔不完备定理 (1931) 给 [希尔伯特计划] 带来了第一次打击，该定理明确指出，在任何基于有限逻辑的一次性选择中，A 的真或假不能等同于 A 或非 A 的可证明性；但原则上仍有可能找到一种机械过程来决定 A、非 A 或两者都不是在给定系统中可正式证明的 [38，第 256 页]。

If as Turing developed the arguments and proofs of “On Computable Numbers” he was not even aware of the relation of Gödel’s results to his own, irony is piled on irony.

如果图灵在发展“论可计算数”的论证和证明时甚至没有意识到哥德尔的结果与他自己的结果之间的关系，那么讽刺就更加讽刺了。