图灵机：在没有计算机的时候，我们如何谈论计算？

1950年10月，一篇题为“机器能思考吗”的论文横空出世。这篇论文中提出了一个令人细思极恐的测试，即在测试者与被测试者（一个真人和一台机器）隔开的情况下，通过通讯装置向被测试者随意提问，并让测试者猜测与自己对话的对方到底是真人还是机器。

在多次测试后，如果机器能平均让每个参与者做出超过30%的误判，那么这台机器就通过了测试，并被认为具有人类智能。

人们第一次意识到机器人可能具备人类智能，便是从此开始。这个测试便是令千万科幻爱好者津津乐道的图灵测试。这篇文章也为作者Alan Turing（艾伦·图灵）赢得了「人工智能之父」的桂冠。

而人工智能之路，或者说计算机发展史的源头，是一篇图灵在24岁时发表的论文。在这篇论文中，他给「可计算性」下了一个严格的数学定义，并提出著名的「图灵机（Turing Machine）」的设想。图灵机不是一种具体的机器，而是一种思想模型，可制造一种十分简单但运算能力极强的计算装置，用来计算所有能想象得到的可计算函数。

因为图灵发明了图灵机，于是时不时便有人跳出来宣称图灵其实「发明了计算机」。然而，图灵机与实际计算机器的设计并不相同。图灵机甚至不是机器的抽象模型。事实证明（有图灵言论为证），图灵机是一个人在桌上的纸张上书写的模型。那么，图灵为什么要发明图灵机，而图灵机又将引领我们去向何方？

1 图灵的论文 “论可计算数”

解答这些疑问的最好办法是把课本放到一边，打开论文。如今，借阅一本1936年的期刊不需要填写借阅卡，也不需要等上一个小时让图书管理员从藏书室取来，我们只需要手捧一杯麦芽威士忌，在家里轻松访问谷歌即可。我们要寻找的那篇图灵论文如下：

论文地址：https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

论文中有一些错误，但瑕不掩瑜。正如Joel David Hamkins所说，图灵将可计算实数（computable real numbers）定义为具有可计算的十进制展开数，这实际上是行不通的，不过修正并不困难。

图灵在标题中就说明了这篇论文的写作意图：“论可计算数及其在「判定问题」中的应用 ”。其中“Entscheidungsproblem（判定问题）”询问是否存在一种有效技术来决定给定的一阶逻辑公式有效，即在所有解释中为真。

图灵将他的想法展开如下:

我们可以把一个正在计算实数的人比作一台只能满足有限数量条件q1，q2，… qR…的机器。这台机器中有一条长长的“纸带”穿过，纸带被分成很多个部分，这种一块一块的部分我们将其称为方块（square），每个方块都能承载一个“符号”…一些写下的符号会形成被计算的实数的十进制的数字序列，而其他的符号则只是“帮助记忆”的粗略笔记。这些粗略的笔记是可以擦掉的。我的论点是，这种在纸带上滑来滑去，滑到某个符号并对这个符号进行相应处理的运算方式，其中包括了所有用于数字计算的运算。

……

“可计算数”简单说来就是，其十进制的表达用有限的手段可计算的实数。按照我的定义，如果一个数的十进制的表达能被机器写下来，那么这个数就是可计算的。

图灵后续进行了定义和证明，这是一篇典型的数学论文，而不是典型的工程论文，在这种文章里读者想看到讨论如何实现文中所描述的某种机制。从图灵的标题和文章中我们可以看出，图灵主要关心的是一个实数到无限位小数的计算。

这篇论文还有许多其他重要贡献：

• 通用图灵机，以及以数字形式为机器编码的想法
• 如此编码的机器的停机问题，以及对角化的不可判定性

写罢这篇论文，图灵打开了理论计算科学领域的大门。

2 通用图灵机

我们不能确定是什么让图灵产生了通用图灵机（UTM）的想法，但一旦他想到了，他可能会认为通用图灵机的存在是显而易见的。因为图灵机的目的就是模拟一个在办公桌上工作的职员，而图灵机的操作和文员行为一样——根据机器状态和磁带符号，根据给定的转换规则列表执行这个或那个操作——显然需要一个图灵机来执行这样的例行任务。图灵的论文对于构造的细节有些粗略，但似乎没有人介意。

而如今，我们有了已经被设计得淋漓尽致的通用图灵机。几十年前，在剑桥大学，Ken Moody 博士编写了一个通用明斯基注册机：

链接：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之间使用了标准的双射，将整数列表打包成单个整数。他编写了一个小型寄存器机器的小库，用于执行堆栈上推和从堆栈弹出等操作，并创建了一个让人想起真实处理器的获取-执行周期的设计。整个过程可见以下几张幻灯片。下图是机器本身：

下图则是机器的整体结构。(这两张图的作者都是剑桥大学理论计算科学教授Andrew Pitts。)

出人意料的是，这个机器的结构真简单！

3 停机问题

停顿问题显然是不可决定的。否则，许多数学上的猜想都会难以解决，比如费马大定理：只要写一个程序，搜索x, y, z, n>2，使，并问它是否终止。然而，停机的不可判定性必须被严格地表达和证明。

与大众看法相反，图灵的论文并没有讨论停机问题，而是讨论了一个与停机问题相关的特性，他称之为“循环性”（circularity）。如果图灵机「只写下有限数量的第一种符号」（即0和1），它就是循环性的。我想，循环性之所以重要，是因为图灵特别喜欢把实数近似为无限的二进制字符串。物理学家Christopher Strachey在1965年给《计算机杂志（Computer Journal）》的一封信中声称，图灵告诉他一个关于停机问题不可判定性的证明。

4 图灵和Maurice Wilkes

2009年9月，David P. Anderson采访了Maurice Wilkes，他对图灵的看法却与大众恰恰相反：

David P. Anderson：你认为图灵1936年发表的判定问题论文的重要性何在？

Maurice Wilkes：我觉得一个工程师会把存储程序（stored program）的想法当成类似三位一体的重要理论，并会说：”这绝对是一流的，就应该按这办法做”。

那篇论文中的思想与我所说的没有任何具有实际意义的区别。他能发表那篇论文已经很幸运了， 我的意思是阿隆佐·邱奇（Alonzo Church）用其他方法得到了同样的结果。

文章地址：https://cacm.acm.org/magazines/2009/9/38898-an-interview-with-maurice-wilkes/fulltext

需要注意的是，在接受采访时，Maurice Wilkes已经96岁高龄了，他本人是著名的计算机先驱，EDSAC（Electronic Delay Storage Automatic Calculator，即电子延迟存储自动计算器）之父。在他这段奇怪的回答中，可以看出他对图灵崇高地位的嫉妒。这两个人显然合不来！我们也看到了Maurice Wilkes对理论的不屑：尽管把机器编码为数字是对存储程序计算机的预期，但图灵的工作是纯粹的数学，没有任何工程意义。图灵对实际的计算机工程很感兴趣，但他多次试图参与到真正的工程里，却屡屡受挫。

而那些关于邱奇的言论又是如何评价的呢?

5 图灵和邱奇在普林斯顿

在图灵做研究的时候，许多研究人员关注的是“有效可计算性”的想法。此处我推荐读者看看邱奇的《初等数论的一个不可解问题》（见下图）。

论文链接：https://www.jstor.org/stable/2371045?origin=crossref

老实说，这篇论文读起来很吃力，但它能带我们身临其境。本文给出了一个λ-演算的定义，一个递归函数的定义(在Kleene（克莱尼）/Gödel（哥德尔）意义上)，以及λ-演算中范式的存在性和等价性的一些不可判定结果。邱奇和克莱尼已经证明了λ可定义函数和递归函数的等价性；而当图灵在普林斯顿的时候，λ可定义函数和图灵可计算函数之间的等价性也得到了证明，于是我们便得到了邱奇-图灵论题，这个论题的指的是有效可计算的函数恰恰是那些数学上等价类中的函数。

6 邱奇-图灵论题正确吗？

正如人们常说的那样，我们无法证明这个论题正确与否，因为「有效可计算」不是一个精确的概念。我们可以把图灵可计算函数看作是一个颇为包容的类，因为其包括了许多在宇宙生命周期内无法计算的函数。借助Ackermann函数，我们可以很容易地得到范例。

Ackermann函数的现代形式如下：

文章链接：https://lawrencecpaulson.github.io/2022/02/09/Ackermann-example.html

如果你定义f(n)=A(n,n)，就不能指望计算出偶数f(4)。g(n)=A(4,n)尽管是原始递归，但几乎无法计算。

尽管在20世纪30年代之前都还没有数字计算机，但有效可计算性的概念已为数学家所熟知。有效性的概念在希腊几何的直线结构和圆规结构中就早已出现，有效性也是判定问题和希尔伯特第十问题的组成部分。与哥德尔的递归函数和邱奇的λ微积分相比，图灵的概念的天才之处在于其显然是正确的。哥德尔自己也不确定他的递归函数是否抓住了计算的思想，我们也不清楚邱奇的想法是否正确。唯有图灵的想法简单而自然。图灵的想法与其他模型在可证明性上是等价的，并为所有这些模型提供了合理解释。他在1937年发表的论文《可计算性和λ-可定义性》中指出了这一事实。

本文旨在证明作者提出的可计算函数与邱奇的λ-可定义函数以及由埃尔布朗和哥德尔所提出的并由克莱尼发展的一般递归函数是相同的。这几个相同的函数都证明了每个X-定义函数都是可计算的，并且每个可计算函数都是一般递归的。

注意，图灵写的是「可计算的」，而我们要写「图灵可计算的」。