数学的不完美之美——阿兰?图灵与图灵机
2017/5/28 中科院之声
编者按：1936年5月28日，图灵的论文《论可计算数及其在判定问题上的应用》被伦敦数学学会接收。在此篇论文中，他提出了著名的“图灵机”的设想。
一、图灵机的起源——一起从逻辑说起
说起图灵机的起源，就要从20世纪初说起，当时数学界的巨人——戴维·希尔伯特(David Hilbert)提出了著名的23个问题。他希望将整个数学体系矗立在一个坚实的地基上，一劳永逸地解决所有关于对数学可靠性的种种疑问。跟图灵机起源相关的可以总结为如下几个问题：
数学是完备的吗？也就是说，面对那些正确的数学陈述，我们是否总能找出一个证明？数学真理是否总能被证明？
数学是一致的吗？也就是说，数学是否前后一致，不会得出某个数学陈述又对又不对的结论？数学是否没有内部矛盾？
数学是可判定的吗？也就是说，能够找到一种方法，仅仅通过机械化的计算，就能判定某个数学陈述是对是错？数学证明能否机械化？
(注：此处参考于《计算的极限(零)：逻辑与图灵机》http://songshuhui.net/archives/70194#comments)
没过多久，1931年，一个名不见经传的年轻逻辑学家库尔特·哥德尔(Kurt G?del)发表了一篇论文，得到了前两个问题的答案。这就是著名的哥德尔不完全性定理。
我们可以表述其为：任何自然数算术理论的公理化系统都是不完全的，存在不可证明，也不可证否的命题。
可以说，哥德尔的不完全性定理与其说回答了希尔伯特的前两个问题，不如说它阐述了为什么我们根本不可能解答这两个问题。自此，证明数学系统一致性和完备性的梦想破灭了。
哥德尔构造了这样的一个命题：“我无法被公理证明”。如果你证明了这个命题，那么这个命题的内容便是不对的，或者说该命题为假。于是，系统是有矛盾的。如果这个命题为真，根据它的内容，你也无法证明它。哥德尔构造了一个描述了本身不可证明的自指命题，通过这个命题完成了他的证明。所以，哥德尔不完全性定理证明了许多问题是不可判定真假的。
那么问题就来了，哪些问题是可判定的，哪些问题是不可判定的呢？
可判定性的问题可以说是计算理论中最具哲学意义的定理之一。
在逻辑中，如果某个逻辑命题是不可判定的，即表明对它的推理过程将一直运行下去，永远都不会停止。
换一个角度，在计算理论中，不可判定问题可以表述为在有限的时间内无法得到解决的问题，也就是说，这些问题是“不可计算”的。如何判定哪些是“可计算”的，哪些是“不可计算”的，“不可计算”问题有如何的层谱和相互关系，这便是可计算性理论的研究内容。
20世纪30年代，许多数学家试图将可计算性理论形式化。1934年，哥德尔在提出了一般递归函数的概念。同年，丘奇提出了“丘奇论点”，递归函数和Lambda可定义函数来形式地描述有效可计算性。
图灵在他的《论可计算数及其在判定问题中的应用》这篇开创性的论文中，提出了著名的“图灵机”的设想。他将逻辑中的任意命题用一种通用的机器来表示和计算，并能按照一定的规则推导出结论，其结果是：可计算函数可以等价为图灵机能计算的函数。换句话说，图灵机能计算的函数便是可计算的函数，图灵机无法计算的函数便是不可计算的函数。
有意思的是，同时期远隔图灵万里的美国数学家丘奇，二者解决了同样的问题，得到了相同的结论，并且可以相互印证正确性。
阿兰?图灵
后来“所有计算或算法都可以由一台图灵机来执行”的观点便被称为“丘奇-图灵论题”。
按照这个思路，我们来继续深入，是否每一个问题都可判定是否可计算？会不会出现像逻辑中的悖论一样有无法判断的问题？
图灵为了解答这个问题，就设计了这么一个能够模拟所有计算的机器，然后证明了：这个机器在有限时间内能够执行完毕问题便是可以判定的问题，这个机器无法在有限时间内执行完毕的便是不可以判定的问题。
说到这里，我们来做一个假设，编写一个图灵机一号，它遍历所有大于等于2的偶数，尝试将这样的偶数分成两个质数的和。如果它遇到一个不能被分解为两个质数之和的偶数，它就停机并输出这个偶数；否则，它就一直运行下去。
我们满心希望的设想，如果图灵机可以解决上述的程序，那么不就解决了三大数学难题之一的哥德巴赫猜想？
三五分钟过去了……五年十年过去了……几十年几百年过去了，程序依然没有运行完毕，那么这个问题到底是无法执行完毕呢，还是时间不够还没有执行完毕？
为了解决这个问题，我们构建一个图灵机二号，它的功能是：判断所有的图灵机是否能在有限时间内执行完毕。
这么说来，只要我们能够判断这一个图灵机是否能够执行完毕，就可以判断所有的图灵机是否能够执行完毕。那么我们大胆构思一个“反例”——图灵机三号，它可以判断自身是否能够执行完毕，并做出相反的行为。
那么问题来了，图灵机二号判断图灵机三号是否可以执行完毕的时候就会出矛盾，图灵机三号总是无法被判断到底是否可以执行完毕。逻辑学中宛若魔咒一般的自我指涉问题同样在图灵机中也体现出来。
举一个经典自我指涉的例子，有位理发师说：“我将为所有不给自己理发的人理发”，那么到底这位理发师给不给自己理发便成为了一个无法解决的命题。
“矛盾的自我指涉”
图灵机二号存在无法判定的图灵机，因此它功能的假设便是不成立的，并没有这么一台图灵机可以判断所有图灵机可以在有限范围内执行完毕。自然图灵机理论无法尽善尽美地判断问题是否都可判定。
这证明图灵机也有无法解决的问题，但是，图灵机的“不完美”通过完备的论证过程证明了不可判定问题的无解，上述这一切的一切最终埋葬了希尔伯特宏伟的数学大厦的计划。
二、图灵机——可计算理论的“副产物”
设想一下，我们在计算乘法的时候：在每个时刻，我们只将注意力集中在一个地方，根据已经读到的信息移动笔尖，在纸上写下符号或数字；而指示我们写什么怎么写的，则是早已背好的九九乘法表，以及简单的加法。
参考维基百科中图灵机的基本思想：
图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：
在纸上写上或擦除某个符号；
把注意力从纸的一个位置移动到另一个位置；
而在每个阶段，人要决定下一步的动作，依赖于(a)此人当前所关注的纸上某个位置的符号和(b)此人当前思维的状态。
图灵机的实现结构并不复杂，它有一条无限长的纸带，纸带由方格组成。有一个读写头在纸带上移来移去，读写头连接控制器，控制器内有状态转移表，还有一些固定的程序。在每个时刻，读写头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。图灵机不断重复上述的步骤，这便是执行的过程。
图灵机理论示意图
如果将一个笔算乘法的人看成一台图灵机，纸带就是用于记录的纸张，读写头就是这个人和他手上的笔，读写头的状态就是大脑的精神状态，而状态转移表则是笔算乘法的规则，包括九九表、列式的方法等等。
三、图灵机意义——探索计算的极限
图灵机模型是目前为止最为广泛应用的经典计算模型。目前尚无找到其它的计算模型(包括量子计算机在内)，可以计算图灵机无法计算的问题。图灵停机问题开启了可计算性理论的序幕，这是计算学科最核心的理论之一。并提出了可以用计算机解决的问题的判定方法，为计算机编程语言的发展奠定了基础。
此外，图灵机为现代计算机提供了理论原型。通用图灵机U，把另外一台图灵机A的编码A’作为输入的一部分，模拟执行A的计算过程，为计算机编程语言的发展奠定了理论基础。一个硬件的机器A，比如，A可能是专门计算加法的机器，被软件A’在U上模拟了；另一个计算乘法机器B，也可通过软件B’在U上模拟实现。只要配上适当的软件，U可以做任何计算。通用图灵机U，是现代通用计算机的理论原型，为现代计算机指明了发展方向，肯定了现代计算机实现的可能性。
数学家冯·诺依曼在图灵机模型的基础上提出了奠定了现代计算机的基础的冯诺依曼架构。这种架构以运算器为中心，输入输出设备和存储器之间的数据传送通过控制器完成。从第一台每秒可以进行数千次计算的埃尼阿克(ENIAC)起，到至今每秒可以进行数亿亿次运算的中国神威·太湖之光超级计算机，几十年现代计算机的发展依旧遵循了冯·诺依曼体系，因此，可以说是冯·诺依曼创造了现代计算机。
中国神威·太湖之光超级计算机
图灵机是对人计算过程的模拟，可以理解为是现代计算机的“灵魂”，而冯·诺依曼计算机则是图灵机的工程化实现，是现代计算机的“肉体”。
感谢中国科学院软件研究所副研究员夏盟佶提供的理论支持
文中部分图片来源于网络
作者靖然翔，系中国科学院软件研究所发展规划与重大任务办公室助理工程师
http://weixin.100md.com
返回 中科院之声 返回首页 返回百拇医药