一个无法证明的逻辑问题

从一个数学的逻辑问题开始讲起。

△ 大卫·希尔伯特。

1900年，德国数学家及逻辑学家大卫·希尔伯特在国际数学大会上发表了题为“数学问题”的演讲，并提出了23道当时待解决的数学问题。这份演讲中提到的23个问题大力推动了整个20世纪的数学发展，并被后世称为希尔伯特的23个问题。其中第十个问题提到，我们是否可以设计一个可行的过程，并通过有限次运算来判定任何多个未知数的整系数方程有无整数解。在提出这个问题之后，希尔伯特大力推崇一个概念，便是让所有数学家都致力去构建数学公理，以至于所有的数学理论都能从这些构建的公理中，通过一个完备且一致的体系得到证明。

为了进一步说明希尔伯特的构想，这里首先阐述一下其构想中提到的三个概念。一个是完备性，即所有数学理论都是可证明的。其次是一致性，即证明结果要么是对，要么是错，不能存在自我矛盾（即对错共同存在）。中学时候学过的反证法便是基于数学理论的一致性所得出的一种证明方法。最后是决定性，即是我们能通过一个可行的过程和有限次运算来证明数学理论。当然希尔伯特所推崇的这个概念是否可行完全取决于他1900年演讲中提到的的第十个问题是否能够被证明为正确。这个问题也使得大批当代数学家趋之若鹜，力图证明希尔伯特提出的构想。而该构想也被命名为“希尔伯特判定性问题”。

△ 库尔特·哥德尔。

这个问题在1931年得到了部分的解答。当时奥匈帝国数学家库尔特·哥德尔在他的论文（On Formally Undecidable Propositions of Principia Mathematica and Related Systems）中提到了一个非常重要的概念——不完备性理论。哥德尔用数学及逻辑学的方法证明出了希尔伯特决定问题中所提出的完备性与一致性无法共存于一个数学系统里。为了理解方便，这里我们举一个简单的例子 。“笔者声明现在我写的这个句子是一句谎话。” 如果你试图去证明这句话的真伪，你会发现，如果这句话是真的，那么我写的这句话就是一句假话，如果这句话是假的，那么我写的这句话就是一句真话，无论从哪个角度来看他们都是相互矛盾的。也就是说如果这句话可被证明真伪（具有完备性），那么得出来的结论必然相互矛盾（不具备一致性）。相反如果要保证证明一致性（没有相互矛盾的结论），那么这句话无论是真还是假，他都是不可以被证明的（不具备完备性）。

这套不完备理论自提出之后在数学及哲学界引起了不小的轰动。自此之后，越来越多的数学问题被证明是不可判定的。数学家们开始人心惶惶，因为谁也不能保证自己辛苦研究几十年的问题不会于未来的某一天在数学系统中被证明为不可判定。哲学家们也开始自我怀疑，因为他们所信奉的绝对真理的体系开始瓦解，因为不完备理论使得他们知道了有些东西我们即使是在理论上也是不可能知道的。

△ 图灵在1936年发表的论文。（图片来源：A.M.Turing）

在哥德尔解决了“希尔伯特判定性问题”中的完备性和一致性的不共存关系之后，这个问题便只剩下了决定性没有得到证明（因为即便是哥德尔证明了不是所有数学理论都是可证明的，也无法证明原来希尔伯特猜想中所提到的通过一个可行的过程及有限次运算来证明数学理论的可行性）。于是这个问题便留到了五年后，在一篇名为“论可计算书机器判定问题上的应用”（On Computable Numbers, with an Application to the Entscheidungsproblem）的论文中得到了最终的解答。没错，这就是图灵享誉世界很重要的一篇论文之一。可能当时连他也不会想到这篇文章中所提到的概念会最终使他从数学和逻辑学系统中开辟出一个全新的分支——计算机。

在“希尔伯特判定性问题”中提到的可行的过程及有限次的运算这些概念属于非常模糊的概念。因为它们在当时没有数学上的一个完整的定义。于是图灵在论文里提出了图灵机这个的概念，用类似有限状态机的原理（注意仅是类似，因为图灵机的功能远超过了有限状态机）定义了“有限次运算”，并用图灵机运算过程定义了“可行的过程”并将之重新命名为“算法”（algorithm）。这便是如今计算机体系结构以及程序算法设计最开始萌芽的地方。接下来我们就来介绍一下图灵机的概念。（值得注意的是，图灵机只是一个概念，并不是一个实体机器。）

如下图所示，图灵机由一个无限长的纸带（TAPE），读写头（HEAD），一套控制读写头移动规则的规则表（TABLE）和一个状态寄存器（REGISTER）组成。

△ 图灵机的结构。（图片来源：Wikipedia）

图中纸带被分为无限个格子，可记录任何字母，二进制数字（0,1）以及空白。每个格子里代表了图灵机的输入和输出信息而空白则表示没有任何信息。下方三角为读写头，表示当先读写（输入输出）的位置。读写头可向左右移动，每次移动一个。其移动方向由当下读写头所指的输入和规则表决定（规则表其实就是当时控制计算机的程序）。读写头首先记录下当下位置的状态（q₁）并存入状态寄存器，然后根据当下输入对比程序中的要求进行左右移动或停留在当下位置，最后根据程序输出字母或数字，修改新的位置的数字或字母。每次工作图灵机的读写头都会从起始位置开始，由规则表和输入控制其移动到不同位置，并最终在程序结束时停留在空白格里。在细心地读者会发现，图灵机的整个构想已经满足了现代计算机所需要的所有基本元素，包括程序，输入输出和存储器。这也是为什么说图灵机奠定了现代计算机发展的基础。因为现在计算机能做的一切事情图灵机都可以做到（图灵机的具体工作例子我们会在今后的文章中慢慢提到）。

图灵在论文中用读写头在受程序和输入控制下进行的移动来定义了希尔伯特判定性问题中的“可行过程”，并用读写头通过有限次移动在程序结束时最终停留在空白格这一过程定义了决定问题中的“有限次运算”。通过这两个定义的设定，希尔伯特的决定性问题就变成了：是否存在这样一个图灵机，使其能判定任意一个程序能否在有限时间内结束运行。这就演变成了另外一个重要的理论——停机理论。

可圈可点的是，图灵用了一种非常简单的办法证明了这一理论的不可证的特性，所用的方法和我们之前提出证明谎言的例子类似。首先我们假设存在这样一个图灵机能够对任意程序作出是否结束运行的判断。先不管该机器内部如何运行，我们假设它能在接收到字符输入（来自纸带）和程序输入（来自规则表）之后输出“是”和“否”。（是代表判定运行可以结束，否代表判定运行不能结束）。我们将该图灵机命名为H。然后我们将H稍作改动，在H输出“是”的时候将输出连接到一个无限的循环程序里，并在H输出“否”的时候直接停止运行。我们把改进后的机器命名为H’。现在我们把H’同时作为H’这个机器本身的字符输入和程序输入，这时会发生什么呢？ 如果H判断“是”那么H’则不会停止，而如果H判断否，那么H’则会停止（注意H’是通过H改变而来的，所以H’包含H）。而我们最开始假设的是机器H总能对程序是否结束运行做出正确的判断。我们由此得到矛盾，从而得到这样的机器H不存在。也就是说，不存在这样一个图灵机能准确的对程序是否结束运行作出判断。而这个证明最关键的一点就是利用了自我干涉的原则和数学系统中的一致性。

至此希尔伯特最早提出来的让所有数学理论都能从数学家构建的公理中得到证明的这一概念被图灵证明了不可行。而图灵在证明整套理论中所提出来的图灵机的概念也为计算机体系结构及程序设计的发展奠定了基石。那么图灵机具体是如何做计算的呢？同时期的其他科学家是否有类似的研究呢？他们和图灵的研究又是如何共同促进了现代计算机及程序的发展呢？且看下回分解。

道法自然/文 原理（principia1687）

喜欢这类内容？也愿意再阅读其内容…？那么敬请关注【博科园】今后我们会努力为你呈现更多科学知识。