# 2.6 阿兰·图灵（Alan Turing）

阿兰·马蒂森·图灵（Alan Mathison Turing）于 1921 年出生在伦敦，从小表现出惊人的数学和科学能力。他对计算机科学的建树始于 1935 年，当时他是剑桥国王学院的硕士生。

## 2.6.1 丘奇-图灵论题

### 可判定性问题

可判定性问题（Entscheidungsproblem, 德语）是由德国数学家大卫·希尔伯特提出的问题：「是否存在一种算法，输入正式逻辑语句输出准确的”是”或”否”答案？」，该算法能回答如“是否有一个数大于所有数”之类的数学问题。

1935 年美国数学家阿隆佐·丘奇（Alonzo Church）首次提出解决方法，其开发了名为「Lambda 算子」（Lambda Calculus）的数学表达系统，证明了该算法不存在。该系统能表示任何计算，但其使用的数学技巧难以理解和使用。

与此同时，阿兰·图灵也提出了一种现在名为「图灵机」（Turing Machine）的假想计算机，其计算能力与 Lambda 算子一致但更为简单，因此在新兴的计算机领域更加受欢迎。

### 图灵机

![图灵机](https://275040345-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FycDQGvckh16RY095vh62%2Fuploads%2FxuBn6utARWnNeFaoQzdE%2F0.png?alt=media)

图灵机

图灵机是一台理论计算设备，由如下部件组成：

1. 纸带：无限长，用于存储符号。
2. 读写头：位于纸带上，可以读取和写入纸带上的符号。
3. 状态变量：用于保存当前变量。
4. 规则：用于描述机器做什么；根据当前状态和读写头中的符号来决定机器的执行 -> 写入符号 or 改变状态 or 移动一格读写头 or 动作组合。

使用图灵机需要定义起始状态和规则，具体示例[参见视频](https://www.bilibili.com/video/BV1EW411u7th?t=154.5\&p=15)。该机器是一台通用计算机，如果有足够的时间和内存（纸带）可以利用规则和状态执行任何计算，这是一个很强大的理论模型。

### 图灵完备

图灵完备（Turing Completeness）是针对一套数据操作规则而言的概念。数据操作规则可以是一门编程语言，也可以是计算机里具体实现了的指令集。当这套规侧可以实现图灵机模型里的全部功能时，就称它具有图灵完备性。（cr.[知乎 @RanC](https://www.zhihu.com/question/20115374/answer/288346717)）

### 停机问题

停机问题（Halt problem）是指“给定图灵机描述和输入纸带，是否有算法确定机器会永远计算下去，还是会在某一点停机？”，图灵证明了其无法解决，推理如下：

![停机问题](https://275040345-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FycDQGvckh16RY095vh62%2Fuploads%2FJD38B7JQPt48xo4jWheg%2F1.png?alt=media)

1. 假想图灵机 H：输入“问题描述 + 纸带数据”，输出 Yes 表示会停机，输出 No 表示不会。
2. 假想图灵机 -H：H 的输出为 Yes，则 -H 的输出为不会停机；H 的输出为 No，则 -H 的输出为会停机。
3. 将 H 和 -H 组成机器，并添加分离器（splitter）使得其只接收一个输入（程序），名为「Bizzaro」(异魔)。

将 Bizzaro 的描述作为其输入（问 H 说当 Bizzaro 的输入是 H 时会如何），则出现悖论：

* H 说 Bizzaro 会停机，则通过 -H 进入无限循环。
* H 说 Bizzaro 不会停机，则输出 No 通过 -H 停机。

图灵证明了有个程序使得图灵机 H 无法判断是否会停机，意味着“停机问题”无法用图灵机解决。

### 可计算性理论

丘奇和图灵对可判定性问题的解答证明了计算机的能力是有极限的，无论有多少的时间或内存，有些问题是计算机无法解决的。

这种对可计算性理论（formalize computability）的讨论，称为「丘奇-图灵论题」（Church-Turing Thesis）。

## 2.6.2 破译英格玛机

从 1936 年至 1938 年，图灵在丘奇的指导下拿到了普林斯顿的博士学位，毕业后回到剑桥。

再之后，图灵加入了英国政府的密码破译组织。1939 年前后，英国卷入第二次世界大战，图灵的才能被投入战争，其工作内容之一是破解德国的通信加密。

在 1.2.3 节我们在讨论巨人一号时，曾提及图灵在该计算机安装地——英国布莱切利园（Bletchley Park）——制作了 Bombe，一种用于破译纳粹英格玛（Nazi Enigma codes）的机电设备。

英格玛机（Enigma Machine）是一种用于加密（Encryption）明文的设备，加密由机器顶部有 26 齿的齿轮组合决定，机器前还有用于互换两字母的插板，总共有上十亿种可能（具体可参见 4.6.1 节）。

Bombe 是图灵在波兰破译专家成果的基础上设计的，其利用了英格玛机的缺陷——字母加密后绝不会是字母自己本身，减少了对加密信息尝试组合的搜索数量。

德国人时不时会升级英格玛机（e.g. 加个齿轮），图灵和他的同事们则努力破解加密。这些解密得到的情报为盟军赢得了许多优势，有些史学家认为他们将战争缩短了好几年。

## 2.6.3 图灵测试

战后图灵回到学术界，为早期计算机工作做出贡献，如曼彻斯特 1 号（早期的存储程序计算机）以及人工智能（Aritificial Intelligence, 1956 年被正式命名，见后）。

1950 年，图灵设想了未来计算机能够拥有和人类一样的智力，或至少难以区分。他提出“若计算机能够欺骗人类相信它是人类，才能算是智能”，这成为智能测试的基础，成为「图灵测试」（Turing Test）。

图灵测试的现代版本称为「公开全自动图灵测试」（a completely automated public Turing Test），用于区分计算机和人类，即常见的「验证码」（Captcha）。

同时，计算机领域的最高奖项「图灵奖」（Turing Award）也以图灵的名字命名。