阿兰·图灵与图灵机
靖然翔
中科院物理所
2017-05-31 10:17:30
转自公众号：中科院之声
编者按：1936年5月28日，图灵的论文《论可计算数及其在判定问题上的应用》被伦敦数学学会接收。在此篇论文中，他提出了著名的“图灵机”的设想。
一、图灵机的起源——一起从逻辑说起
说起图灵机的起源，就要从20世纪初说起，当时数学界的巨人——戴维·希尔伯特（David Hilbert）提出了著名的23个问题。他希望将整个数学体系矗立在一个坚实的地基上，一劳永逸地解决所有关于对数学可靠性的种种疑问。跟图灵机起源相关的可以总结为如下几个问题：数学是完备的吗？也就是说，面对那些正确的数学陈述，我们是否总能找出一个证明？数学真理是否总能被证明？数学是一致的吗？
也就是说，数学是否前后一致，不会得出某个数学陈述又对又不对的结论？数学是否没有内部矛盾？数学是可判定的吗？也就是说，能够找到一种方法，仅仅通过机械化的计算，就能判定某个数学陈述是对是错？数学证明能否机械化？没过多久，1931年，一个名不见经传的年轻逻辑学家库尔特·哥德尔（Kurt Gödel）发表了一篇论文，得到了前两个问题的答案。这就是著名的哥德尔不完全性定理。
我们可以表述其为：任何自然数算术理论的公理化系统都是不完全的，存在不可证明，也不可证否的命题。可以说，哥德尔的不完全性定理与其说回答了希尔伯特的前两个问题，不如说它阐述了为什么我们根本不可能解答这两个问题。自此，证明数学系统一致性和完备性的梦想破灭了。
二、图灵机——可计算理论的“副产物”
设想一下，我们在计算乘法的时候：在每个时刻，我们只将注意力集中在一个地方，根据已经读到的信息移动笔尖，在纸上写下符号或数字；而指示我们写什么怎么写的，则是早已背好的九九乘法表，以及简单的加法。
图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：在纸上写上或擦除某个符号；把注意力从纸的一个位置移动到另一个位置；而在每个阶段，人要决定下一步的动作，依赖于（a）此人当前所关注的纸上某个位置的符号和（b）此人当前思维的状态。
三、图灵机意义——探索计算的极限图灵机模型是目前为止最为广泛应用的经典计算模型。
目前尚无找到其它的计算模型（包括量子计算机在内），可以计算图灵机无法计算的问题。图灵停机问题开启了可计算性理论的序幕，这是计算学科最核心的理论之一。并提出了可以用计算机解决的问题的判定方法，为计算机编程语言的发展奠定了基础。此外，图灵机为现代计算机提供了理论原型。通用图灵机U，把另外一台图灵机A的编码A’作为输入的一部分，模拟执行A的计算过程，为计算机编程语言的发展奠定了理论基础。
一个硬件的机器A，比如，A可能是专门计算加法的机器，被软件A’在U上模拟了；另一个计算乘法机器B，也可通过软件B’在U上模拟实现。只要配上适当的软件，U可以做任何计算。通用图灵机U，是现代通用计算机的理论原型，为现代计算机指明了发展方向，肯定了现代计算机实现的可能性。数学家冯·诺依曼在图灵机模型的基础上提出了奠定了现代计算机的基础的冯诺依曼架构。
这种架构以运算器为中心，输入输出设备和存储器之间的数据传送通过控制器完成。从第一台每秒可以进行数千次计算的埃尼阿克(ENIAC)起，到至今每秒可以进行数亿亿次运算的中国神威·太湖之光超级计算机，几十年现代计算机的发展依旧遵循了冯·诺依曼体系，因此，可以说是冯·诺依曼创造了现代计算机。
图灵机是对人计算过程的模拟，可以理解为是现代计算机的“灵魂”，而冯·诺依曼计算机则是图灵机的工程化实现，是现代计算机的“肉体”。