> For the complete documentation index, see [llms.txt](https://cccs.viyi.cc/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cccs.viyi.cc/2-cheng-xu-she-ji/2.6-alan-tu-ling-alan-turing.md).

# 2.6 阿兰·图灵（Alan Turing）

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

## 2.6.1 丘奇-图灵论题

### 可判定性问题

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

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

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

### 图灵机

![图灵机](/files/nmNZ1FffOK1UO2ZhLsE4)

图灵机

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

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）是指“给定图灵机描述和输入纸带，是否有算法确定机器会永远计算下去，还是会在某一点停机？”，图灵证明了其无法解决，推理如下：

![停机问题](/files/2DLrZzPN5tjQHoKaOqb7)

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）也以图灵的名字命名。


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://cccs.viyi.cc/2-cheng-xu-she-ji/2.6-alan-tu-ling-alan-turing.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.