当前蓬勃发展的人工智能揭示出人类面对自身的挑战，当我们从中认识到人类社会出现重大转折时却似乎失去了方向感，比如，人工智能的可解释性一直是一个“黑盒子”。因此，我们认为，追本溯源重读图灵的著作对理清一直以来困扰人们的数理逻辑和计算机理论的基本难题会有实质性的帮助！

图灵1936年论文为计算机技术和科学奠定的基础，这里简介此论文。

图灵1936年的论文正如其题目所示，“论可计算数及其在判定问题上的应用（On Computable Numbers, with an Application to the Entscheidungsproblem）”。图灵开篇提出“可计算数”：

- 可计算数简单被描述成实数，表达成用有限的手段计算的十进制数。虽然本文的主题表面上讲可计算数，然而几乎可以同样容易定义和研究变量为整数或实数或可计算变量的可计算函数，可计算谓词等。在每种情况下，基本的问题是一样的，我选择可计算数来解释，是因为这样可以涉及最少的技术细节。

图灵将人计算实数与机器计算比较，引入“计算机器”（现称“图灵机”），这样计算机器的“可计算性”就可由“可计算数”来表达。然而由于可计算数是一个不可分割的整体，由此定义的可计算性因此具有整合性，使得图灵得以持系统观建立其可计算性理论，这具有“范式”意义的面向，图灵在论文中并没有特别的强调。

Entscheidungsproblem源自希尔伯特（Hilbert）在1900年巴黎国际数学家大会上提出的23个数学问题中的第10个问题 - 判定丢番图方程的可解性。Entscheidungsproblem在一阶谓词系统中的一般表述是问：是否存在判定给定一阶谓词公式可证明的通用过程？

一个计算机器是否具有可计算性，即是否打印出预期的可计算数，是需要判断的，这就是图灵这篇奠基性的论文的主题：证明“可计算性是不可判定的”，进而证明Entscheidungsproblem无解。

图灵证明的重点在第8章“对角线法的应用”。图灵首先用前面7章的篇幅为第8章作准备：设计计算机器，设计“模拟任意机器计算的通用计算机器”（“通用图灵机”），定义可计算性（circle-free machine vs circular machine） ，为枚举可计算数提出机器的编码等；然后，在第8章，图灵应用对角线法证明不存在“判定任意机器的可计算性的通用计算机器”；最后在论文的第11章“应用于判定问题”，图灵运用第8章的结果证明Entscheidungsproblem无解。

图灵的论文共有11章：

1. 计算机器（Computing machines）

图灵可将一个人计算实数与一台机器计算比较，引入了计算机器的概念，并为他的计算理论模型（现在称为“图灵机”）的发展奠定了基础。

2. 定义（Definitions）

图灵定义基本概念，自动机（Automatic machines），计算机器（Computing machines），循环和非循环机器（Circular and circle-free machines），可计算序列和可计算数（Computable sequences and numbers）。

3.计算机器的例子（Examples of computing machines）

图灵提供了两种计算机器的例子：第一个计算序列 010101… 的机器；第二个计算稍微困难一些等序列，001011011101111011111

4. 缩写表（Abbreviated tables）

图灵引入了缩写表的概念，作为更简洁地表示计算机操作的一种手段。

5. 可计算序列的枚举（Enumeration of computable sequences）

基于可计算序列是由机器计算的事实，图灵提出了一种对机器进行编码的方法，首先将其表示为“标准描述（S.D）”，然后将标准描述表示为称为机器的“描述数（D.N）”的整数 ，使得枚举机器以及可计算数成为可能。

6. 通用计算机器（The universal computing machine）

图灵引入了“通用图灵机”的概念，这一关键思想强调了单个图灵机模拟任何其他图灵机的能力。

7. 通用计算机器详细说明（Detailed description of the universal machine）

图灵对通用计算机的构造和操作进行了详细的技术阐述，解释说明机器如何模拟任何其他机器的行为。

8. 对角线过程的应用（Application of the diagonal process）

图灵首先应用对角线法证明不存在“判定任意机器的可计算性的通用计算机器”；然后图灵利用机器D不存在的结果进一步指出，“不存在机器E，当给它提供任意机器M的S.D时，判定M是否打印一个给定的符号（比如0）”，这才是所谓的“停机问题”。换句话说，“停机问题”不过是“不存在判定任给机器的可计算性的通用过程（机器D）”的推论。

9. 可计算数的范围（The extent of the computable numbers）

图灵讨论三种类型的论证有助于理解可计算数的范围：直觉、证明和示例。

10. 可计算数的大类例子（Examples of large classes of numbers which are computable）

图灵指出某些大的类的数是可计算的，它们包括代数数的实数部分，Bessel函数的大小的实数部分，PI, e等等。

11. 应用到 Entscheidungsproblem （Application to the Entscheidungsproblem） 

图灵将每个计算机M表达为一个谓词公式Un(M)，证明如果存在一个通用过程来确定Un(M)是否可证明，那么也存在一个通用过程来确定M是否打印过0；而第8章证明这样的通用过程不存在，所以也就不存在通用过程证明给定的谓词公式是否可证明，于是希尔伯特问题无解。

Reference :

Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem, 1936.  https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf