大家好，我是大老李。不久前在大老李的微信群中，有一位听众转了我一篇文章，是关于2016年国外研究者发表的一篇论文，这位研究者开发出了一个电脑程序，理论上，可以在有限的时间内，验证包括哥德巴赫猜想和黎曼猜想的正确性。

这篇论文中的发现非常有意思，我很想介绍给大家。但是看懂这篇论文需要的准备知识比较多，好在多数准备知识在大老李之前的节目中都或多或少提过了，比如哥德尔不完备定理，ZFC公理体系等。但欠缺的有关图灵机（Turing Machine）的介绍，所以今天先给大家介绍下图灵机。

照例，大老李在介绍一个概念前，要先介绍下为什么要有这个概念。图灵为什么要提出图灵机这个概念呢？目的之一是为了回答希尔伯特和他的学生阿克曼（Wilhelm Ackermann）在1928年提出的一个问题：

是否存在一个算法，对某种形式化语言（Formal Language）中的逻辑命题，能够判断该命题的真假，并最终输出判断结果。这个问题后来被称为“可判定性问题”（Entscheidungsproblem）。

我知道你听了这个问题后还是一头雾水，什么叫“形式化语言”，这里的“逻辑命题”和“算法”又是啥？那我继续回溯一点历史。这个问题最早可以追溯到17世纪的莱布尼兹。莱布尼兹在帕斯卡的发明基础上，改进设计并制造了一台用机械装置驱动的计算机械：

莱布尼兹还进一步设想，如果将来有一个机器不但能做数学运算，还能做逻辑推理就太棒了。只要直接“告诉”机器你的数学命题，机器能告诉你这个命题正确与否。而且，莱布尼兹还意识到，要达到这一目标，首要的一步的就是需要有一种机器可以读取的“Formal Language”，现在被翻译成“形式化语言”。

我想听众中可能也有不少人有过这种设想：数学证明的过程，如果全部用符号表示出来，似乎就是一种符号游戏了，甚至于都不需要理解符号所表示的实际意义。如果能把数学命题的证明，变成一种有规律可循的符号游戏，那可以让计算机去全权处理，数学家也就都下岗了。

但目前离这一目标还相差很远，现在能做的最好的也就是让机器去检查一个“证明”。我之前介绍“开普勒猜想”的文章中提到过，黑尔斯为了证明他的证明完全正确，不惜再用11年时间，用群体协作的方法，把他原来的证明用形式化语言重写了一次，然后交给机器证明检查软件，最终确认了他的证明正确。

(形式化证明代码的例子，摘自 https://github.com/flyspeck/ ，黑尔斯关于开普勒猜想的证明代码库)

说句题外话，关于现在闹得沸沸扬扬的日本京都大学望月新一教授所发表的，多数人看不懂的“abc猜想”的证明。如果有人能把望月教授的证明改写为形式化证明，交给机器检查，那么所有争议就都解决了。只是这个工作量，大概要以几十年起步，所以不知道有没有人肯这么去做。当然要去做，也只有懂望月那套理论的人去做了。这是题外话。

总之，莱布尼兹提出了有关机器证明的初步设想，并提出需要确立一种形式化语言。到十九世纪末，二十世纪初，数学家在数学公理化的工作方面做了很多工作，主流数学家接受了以策梅洛-弗兰克尔集合论，加选择公理所构成的ZFC公理系统，作为数学的逻辑推理基础。把皮亚诺算术公理作为数学研究对象的定义基础。这两套公理构成了数学大厦的地基。

1900年，德国数学家希尔伯特发布了他著名的“二十世纪重大的23个数学问题”，从他发布的问题来看，希尔伯特对构建完美的数学基础是充满希望的。其中第10个问题是：

对于一般的丢番图方程，能否通过某个确定的算法，经过有限的步骤，判定这类方程是否有整数解。

丢番图方程就是那种未知数比方程个数多的那种方程，一般这种方程都有无穷多个解。但是我们经常会加入只考虑整数解得情况，比如“费马大定理”所考虑的也是一种丢番图方程。看的出，希尔伯特的这个问题就是对机器证明问题的一个特例。

虽然在第二年，罗素悖论被发现，但希尔伯特认为这无伤大雅，毕竟罗素悖论里这种自指向的命题，怎么看都不像数学里正经需要研究的命题。所以，1928年，希尔伯特还把1900年提出的第十个问题一般化了：有没有算法，可以在有限步骤内，对任意的形式化的数学命题进行真或假的判断？

这里“形式化”的命题我再稍微举个例子，便于大家理解。各位想必都有体会，数学里的命题都有“题设”和“结论”两部份，因为有了某个题设，所以导致某个结论。而题设和结论部分又往往是由若干“存在”或“对任意”这两个词开始的句子。比如哥德巴赫猜想是说：

对任意大于2的偶数，存在两个质数，其和等于这个偶数。

可以发现，只要把“存在”和“对任意”这两个词用符号表示出来，，那么数学命题就很容易全用符号表示出来。而数学家确实发明了两个符号去表示这两个词，谓词逻辑中称为“量化符号”。比如哥德巴赫猜想就变成：

\forall偶数a>2 ，\exist质数c,d，c+d=a。

这里我还是用了一些文字，比如“偶数”和“质数”。但是偶数和质数的定义很容易再用其他符号表达出来。你把这些符号全部输电脑，电脑是可以处理的，虽然电脑完全不理解符号后面所表达的真实含义。

以上这种符号表达出来的命题，就是形式化的一阶逻辑命题。

再插个题外话，解释下什么是“二阶逻辑”。一阶逻辑中，“存在”和“对任意”这两个量化符号后面，只能跟一个一般的陈述语句，术语称为“断言”。但如果允许“存在”和“对任意”后面跟另外一个一阶逻辑，那么整个命题就是一个二阶逻辑命题。好像是:

看上去就是一阶逻辑的递归。当然，你大概从没有看到过这种形式的数学命题。确实，数学中的命题大概99.9%以上都可以用一阶逻辑描述出来。倒是有些用一阶逻辑可以描述的命题，必须用二阶逻辑才能证明，就比如我之前节目介绍过的“加强的有限拉姆齐定理”。

扯了那么多背景介绍，终于可以介绍什么是图灵机了。图灵机是有这样一种性质的数学概念：所有一阶逻辑命题真伪性的判定问题，都可以转化为判定一个图灵机是否“停机”的问题。进而图灵又证明了不存在一个一般的判定图灵机是否停机的算法，从而否决了希尔伯特寻找一种通用算法进行命题真伪判断的梦想。

在理解图灵机之前，要先确立一种观念：图灵机不是一种机器，它是完全用合法的数学语言定义出的数学概念。我们说它是一种机器，是方便我们理解，但本质 上，它是数学中的定义。有些媒体把图灵在二战期间发明的破解德军加密装置，英尼格玛机，的机器称为“图灵机”，这就错的太离谱了。事实上，图灵发表有关图灵机的论文是在1936年，二战还要3年后再发生。

我这次介绍图灵机，还是先从臆想中图灵机外观开始说起，便于各位理解。根据多数科普书中的介绍，图灵机是这种样子：

它有一条长长的纸带，理论上是无限长的，纸带上划分了很多小方格子。你可以把这条纸带想象成电脑硬盘存储，每个格子就是图灵机每次操作可以存取的单元大小。

某个格子上方有一个可以读取格子内信息或写入信息的装置，称为“读写头“。读写头可以在纸上移动，但是只能一格格移动。如果纸带是硬盘的话，那这种硬盘效率是极低的，但没关系，图灵机的设计目标并不是计算效率，而是对计算过程的抽象和简化。

读写头内部本身能保存一个称为“状态”信息，而图灵机就是能根据当前纸带位置上的信息以及内部状态，来决定读写头在当前纸带的格子上做怎样的输出，然后让读写头向哪个方向移动，以及内部状态如何变化的一个装置。

下面说说图灵机在数学中的定义。

数学里，用了七个属性描述图灵机，就是这七个属性，唯一决定了一台图灵机。七个属性看上去有点多，但最主要其实是两个属性：

第一个属性叫：符号（Symbol）集合，即这台图灵机可以在纸带上读取和写入的符号种类，必须是有限的。所有的符号种类数量称为这台图灵机的“符号数”，或者“颜色数”，简称“色数”。这里，符号具体的样子是无所谓的，我们只关心有多少种符号。其中我们还默认有一种称为“空白”的符号，就是纸带上是空的，这种“空白”也算一种符号，也计算在符号集合里。所以，一般符号集合至少有2个元素，其中一个是空白符。

第二个属性叫：状态（State）集合，即这台图灵机内部可以处于哪种状态，也必须是有限的。所有的状态种类数量称为这台图灵机的“状态数”。同样，这里，具体状态表示什么含义是无所谓的，我们只关心有多少种状态，最少是1种状态都行。同样，我们还默认有一种称为“停机”的状态，就是图灵机运算结束，机器停下来的状态。但这种状态一般不计算在状态集合里。

以上就是图灵机最主要的两种属性，其他五种属性是这样的：

第一个就是前面提到的空白符。这个空白符存在是有必要性的，它其实是可以帮我们区分纸带上每一部分信息的边界在哪里。记得之前我在讲信息熵的时候提到，如果只有一个符号是传递不了信息的。就有人说一个符号也可以传递信息，可以用这个符号的数量来表示不同信息。但此时你会发现，必须用空白符。否则你给我发了100个“A”，我怎么知道这些“A”该怎么断开？所以空白符是一个必要符号。

第二个属性是初始输入，即图灵机运行前，纸带上的符号状态。

第三个属性是初始状态，即图灵机运行前，内部所处于的某个状态。任何时刻，图灵机只能处于一个状态。

第四个属性是：“接受状态”，或者叫“终止状态”。也即是图灵机进入这种状态后停机。很多情况下，这个接受状态只有一种，就是之前提到过的停机状态。

第五个属性是：转移函数集合。转移函数很像是计算机的程序，它决定了图灵机的变化过程。图灵机在任何时刻，它所处于的情形是由两个属性确定的：当前读取头下小方格内的符号和内部状态。转移函数因为是函数，它有输入参数和输出参数。它的输入参数就取这两个属性的值，它的输出参数有三个：

所有转移函数的集合就决定了一个图灵机从启动到停机的过程，如果它会停机的话。当然，有些图灵机是不会停机的，比如它进入某几个状态的循环或者读取头永远向右移动等等。

以上就是图灵机全部7个属性，我知道你听的有点晕，但我发现算盘其实是可以模拟成一个图灵机的。算盘的每一档可以看做图灵机的纸带上的一个格子。横档上的两个算珠可以表示0-3三种符号，可以认为0表示空白符。而横档下的5个算珠可以表示0-5，6种状态。所以算盘可以看做一个3符号，6状态的图灵机。

如果你在纸上写好所有符号和状态组合下，也就是3*6=18条转移函数，那么你就完成了一台图灵机的定义，可以在算盘上模拟图灵机的运算。

现在用算盘演示上述图灵机的运算过程。用算盘横档上方的算珠表示颜色，下方算珠表示状态。算盘横档上方一共有2颗算珠，最多可以表示3种颜色；下方算珠有5颗算珠，最多可以表示6中状态。

本例中，因为只要演示2色-4状态的图灵机，因此只需要使用上方的1颗算珠。算珠在上表示色号0，在下表示色号1。同理，使用下方3颗算珠表示0-4号状态。

开始时：

之后的推演留个读者，这台图灵机永不停机......

你能看的出来，图灵机的计算能力是非常简陋的，但妙就妙在图灵证明了，所有一阶逻辑下的数学命题，都可以转化为一个图灵机，而这个命题的真与假，取决于这个图灵机能否进入停机状态。如果停机了，我们就能从这个图灵机的输出中得知这个命题是真还是假。

其实之前在哥德尔不完备定理的节目中提到过，哥德尔其实是证明了“万物皆数字”，所有数学命题都对应一个数字，而图灵有点像证明了“万物皆图灵机”。

证明了“万物皆图灵机”之后就好办了，希尔伯特的“可判定性问题”就变为， 是否存在一个算法，在有限步骤内，去判断任何一个图灵机在给定输入的情况下，运行后是否能停机。图灵证明了，这样的算法是不存在的。证明方法是大家熟悉的罗素悖论模式：

假设有这种通用判别算法，叫它算法P。那么定义一种这样的图灵机，称为U，这个图灵机接受另一个图灵机T和某个输入作为它自身的输入。U的运行模式是：

调用P，把U接收到的图灵机T和输入传递给P。如果P判断T不会停机，则U停机。如果P判断T能停机，则U进入死循环。

现在问题来了， 既然U也是一台图灵机，则把U本身传递给U作为参数会如何？你自己稍微推想下，就会发现这里面的矛盾，U停与不停都不行，所以就不能有这样的算法P。以上这个问题就被称为“图灵机停机问题”。

总之，图灵用图灵机作为工具，证明了希尔伯特所希望的通用命题真伪判断算法是不存在的。但要注意一点的是，虽然一般的图灵机的停机问题是不可判定的，但不表示所有的图灵机的停机是不可判定。

现在已经证明，对四个状态以内的图灵机，都是可判定的。四个状态时的情况还不知道。从5状态开始，猜想都是不可判定的了。再比如，如果你将一个已经证明的数学命题正确编码成图灵机，则不管这个图灵机有多少状态，那么它必然可以停机。

总结一下要点：

图灵机有两个主要参数，符号和状态。

判断数学命题的真伪问题可以转化成判断图灵机是否停机问题，但是不存在一个通用算法去判断图灵机是否会停机。

图灵也用图灵机证明了希尔伯特的“可判定问题中”提出那种算法是不存在的。

今天内容那么多，其实都是为了下一期节目的准备知识，下一期才是重头戏，敬请期待。

参考链接：

https://mathworld.wolfram.com/HaltingProblem.html

https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

https://en.wikipedia.org/wiki/Turing_machine

https://en.wikipedia.org/wiki/Entscheidungsproblem

Turing Machine -- from Wolfram MathWorld