www.ydisp.cn/oss/202207/13/f133e48607ad490ff5f369e778fcb5071c976a.png"alt="image"title="image"style="visibility:可见;宽度：645.017px；height:449px;"data-type="inline">论文地址：https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf论文中有些错误，但瑕不掩瑜隐瞒。正如JoelDavidHamkins所说，图灵将能够计算实数（computablerealnumbers）定义为具有可计算的小数展开式，这实际上是不可行的，但修正并不困难。图灵解释了写这个的目的标题中的论文：“关于可计算数及其在”“决策问题”中的应用。其中“Entscheidungsproblem（决策问题）”询问是否存在一种有效的技术来确定给定的一阶逻辑公式是否有效，即是的，在所有解释中都是正确的。图灵将他的想法发展如下：我们可以将计算实数的人与一台只能满足有限数量条件q1,q2,...qR....的机器进行比较。有一条长长的“纸带”穿过这台机器，胶带是divi分为很多部分，我们称之为方块，每个方块可以携带一个“符号”......一些书面符号将形成正在计算的实数的小数点其他符号只是“帮助记忆”的粗略注释。这些粗略的笔记可以擦除。我的论点是，这种在纸带上左右滑动，滑动到一个符号和对这个符号进行相应处理的操作方法，包括了数值计算的所有计算。...“可计算数”只是一个实数，其十进制表达式可以通过有限的方式计算。根据我的定义，如果一个数的十进制表示可以被机器写下来，那么这个数就是可计算的。图灵随后定义并证明了它。这是一篇典型的数学论文，而不是典型的工程论文。在本文中，读者希望看到对如何实现文中描述的某些机制的讨论。从图灵的题目和文章中我们可以看出，图灵主要关注的是实数到无穷小数位的计算。该论文还有许多其他重要贡献：通用图灵机，以及以数字形式编码机器的想法如此编码的机器的停机问题，以及对角化的不可判定性在写完这篇论文之后，图灵打开了理论通往计算科学领域。2通用图灵机我们不确定是什么让图灵产生了通用图灵机(UTM)的想法，但一旦他想到这一点，他可能认为通用图灵机的存在是显而易见的。因为图灵机的目的是模拟一个在办公桌前工作的职员，而图灵机的行为就像一个职员——根据给定的转换规则列表执行这个或那个操作，这取决于机器的状态和符号在磁带上——显然需要一台图灵机来执行这样的例行任务。图灵的论文对构造的细节有些粗略，但似乎没有人介意。今天，我们拥有一台经过充分设计的通用图灵机。几十年前在剑桥大学，KenMoody博士写了一个通用的Minskykeygen：链接：http://www.igblan.free-online.co.uk/igblan/ca/minsky.html这样的机器有有限的寄存器，每个都可以存储任意大的非负整数。它有一个由三种不同类型的标记指令组成的有限程序：递增寄存器R并跳转到标记L，或R+→L测试/递减寄存器R并跳转到标记L0/L1，或L0←R?→L1中断。这样的机器比图灵机更容易编程，尽管它们看起来仍然不像真正的计算机。Moody使用N和N×N之间的标准双射将整数列表打包为单个整数。他编写了一个由小型寄存器机组成的小型库来执行堆栈压入和弹出等操作，并创建了一个让人联想到真实处理器的获取-执行周期的设计。整个过程可以在下面的幻灯片中看到。下图是机器本身：下图是机器的整体结构。（两幅图的作者都是剑桥大学理论计算科学教授AndrewPitts。）令人惊讶的是，这台机器的结构真的很简单！3.停机问题停机问题显然是不可判定的。否则，很多数学猜想将难以解决，比如费马大定理：只要写一个程序，搜索x,y,z,n>2,so，并询问是否终止。然而，停机的不可判定性必须得到严格的表达和证明。与流行的看法相反，图灵的论文并没有讨论停机问题，而是讨论了与停机问题相关的一个属性，他称之为“循环性”。如果图灵机“仅写入有限数量的第一类符号”（即0和1），则它是循环的。我认为，循环性之所以重要，是因为图灵特别喜欢将实数近似为无限二进制串。物理学家ChristopherStrachey在1965年写给《计算机杂志（Computer Journal）》的一封信中声称，图灵告诉他一个停止问题不可判定性的证明。4图灵和莫里斯·威尔克斯2009年9月，大卫·P·安德森采访了莫里斯·威尔克斯。他对图灵的看法与公众的看法恰恰相反：DavidP.Anderson：你认为图灵1936年关于决策问题的论文的重要性在哪里？MauriceWilkes：我认为一个工程师会把存储程序的想法当作三位一体的大理论，然后说，“这绝对是一流的，应该这样做”。该论文中的想法与我所说的没有任何实际差异。他很幸运能发表那篇论文，我的意思是阿朗佐丘奇用其他方法得到了相同的结果。文章地址：https://cacm.acm.org/magazines/2009/9/38898-an-interview-with-maurice-wilkes/fulltext需要说明的是，采访时MauriceWilkes已经96岁了老的。他本人是著名的计算机先驱，EDSAC（ElectronicDelayStorageAutomaticCalculator，电子延迟存储自动计算器）之父。从他奇怪的回答中可以看出他对图灵崇高地位的嫉妒。这两个明显不合得来！我们还看到莫里斯·威尔克斯(MauriceWilkes)对理论的蔑视：虽然将机器编码成数字是存储程序计算机所期望的，但图灵的工作是纯数学，没有任何工程意义。图灵对实际计算机工程非常感兴趣，但他多次尝试参与实际工程，但屡屡受挫。那些关于教会的言论呢？5图灵和丘奇图灵在普林斯顿做研究的时候，很多研究者都把注意力集中在“有效可计算性”的思想上。在这里推荐读者看看秋琪的《初等数论的一个不可解问题》（见下图）。论文链接：https://www.jstor.org/stable/2371045?origin=crossref说实话，这篇论文读起来有点难，但能给我们带来切身感受。本文给出了λ演算的定义，递归函数的定义（Kleene/G?del意义上的），以及λ演算判断结果中范式的存在性和等价性的一些不一致。Church和Kleiney证明了λ可定义函数和递归函数的等价性；图灵在普林斯顿的时候，也证明了λ-可定义函数和图灵可计算函数的等价性，于是我们得到了Church-Turingthesis，即高效可计算函数正是数学等价类中的那些函数。6Church-Turing论题是否正确？正如人们常说的，我们无法证明这个论点是对还是错，因为“有效可计算”并不是一个精确的概念。我们可以将图灵可计算函数视为一个相当包容的类，因为它包含许多在宇宙生命周期内无法计算的函数。借助阿克曼函数，我们可以很容易地得到例子。阿克曼函数的现代形式如下：文章链接：https://lawrencecpaulson.github.io/2022/02/09/Ackermann-example.html如果定义f(n)=A(n,n)，你不能指望计算得到一个偶数f(4)。g(n)=A(4,n)几乎不可能计算，尽管有原始递归。尽管直到1930年代才出现数字计算机，但高效可计算性的概念为数学家所熟知。有效性的概念已经出现在希腊几何的线性结构和罗盘结构中，有效性也是判断问题和希尔伯特第十问题的一部分。与哥德尔的递归函数和丘奇的λ演算相比，图灵概念的妙处在于它显然是正确的。哥德尔本人并不确定他的递归函数是否抓住了计算的思路，也不清楚丘奇的思路是否正确。只有图灵的想法是简单自然的。图灵的想法可证明等同于其他模型，并为所有这些模型提供了合理的解释。他在1937年发表的论文《可计算性和λ-可定义性》中指出了这一事实。该论文的目的是证明作者提出的可计算函数与Church的λ-可定义函数以及Elbrun和G?del提出的一般递归函数相同由Kleinyi开发。这些相同的几个函数都证明每个X定义函数都是可计算的，并且每个可计算函数通常都是递归的。注意图灵写的是“computable”，而我们要写的是“Turingcomputable”。
