计算机基础课第 33 期分享
01
计算机科学之父—阿兰·图灵
前几节我们聊了基础，比如函数，算法和数据结构，今天，我们来看一位对计算机理论贡献巨大的人，计算机科学之父——阿兰·图灵。
阿兰·马蒂森·图灵 于 1921 年出生在伦敦，从小就表现出惊人数学和科学能力。他对计算机科学的建树始于 1935 年，当时他是剑桥国王学院的硕士生，他开始解决德国数学家 大卫·希尔伯特提出的问题叫 Entscheidungsproblem （德语）即"可判定性问题"：是否存在一种算法，输入正式逻辑语句， 输出准确的"是"或"否"答案？如果这样的算法存在， 可以回答比如 "是否有一个数大于所有数"？我们知道答案：不, 没有。
但有很多其他数学问题，我们想知道答案，所以如果这种算法存在, 我们想知道。美国数学家 阿隆佐·丘奇于 1935年首先提出解决方法，开发了一个叫"Lambda 算子"的数学表达系统，证明了这样的算法不存在。虽然"Lambda 算子"能表示任何计算，但它使用的数学技巧难以理解和使用。
02
图灵机
同时在大西洋另一边，阿兰·图灵想出了自己的办法来解决"可判定性问题"，提出了一种假想的计算机，现在叫"图灵机"。图灵机提供了简单又强大的数学计算模型，虽然用的数学不一样，但图灵机的计算能力和 Lambda 算子一样。同时因为图灵机更简单，所以在新兴的计算机领域更受欢迎。
因为它如此简单，我现在就给你解释。图灵机是一台理论计算设备，还有一个状态变量，保存当前状态。还有一组规则，描述机器做什么，规则是根据 当前状态+读写头看到的符号，决定机器做什么。结果可能是在纸带写入一个符号或改变状态，或把读写头移动一格或执行这些动作的组合。
为了更好理解，讲个简单例子：让图灵机读一个以零结尾的字符串，并计算 1 的出现次数是不是偶数。如果是, 在纸带上写一个 1，如果不是，在纸带上写一个 0。
首先要定义"图灵机"的规则：如果当前状态是"偶数", 当前符号是 1，那么把状态更新为"奇数"，把读写头向右移动。如果当前状态为偶数，当前符号是 0，意味着到了字符串结尾。那么在纸带上写一个 1，并且把状态改成停机(halt)，状态改为"停机" 是因为图灵机已完成计算。
但我们还需要 2 条规则，来处理状态为奇数的情况，一条处理 奇数 + 纸带是 0 的情况。最后，要决定机器的初始状态，这里定成"偶数"定义好了 起始状态+规则，就像写好了程序，现在可以输入了，假设把"1 1 0"放在纸带上，有两个 1，是偶数。注意，规则只让读写头向右移动，其他部分无关紧要，为了简单所以留空。
"图灵机"准备好了，开始吧。
机器起始状态为"偶数"，看到的第一个数是 1，符合最上面那条规则，所以执行对应的步骤，把状态更新到"奇数"。读写头向右移动一格，然后又看到 1, 但机器状态是"奇数"，所以执行第三条规则，使机器状态变回"偶数"。读写头向右移动一格，现在看到 0，并且机器状态 偶数所以执行第二条规则。在纸带上写 1，表示"真" 的确有偶数个 1，然后机器停机。
这就是图灵机的原理，很简单对吧？你可能想知道 有什么大不了的，图灵证明了这个简单假想机器，如果有足够时间和内存，可以执行任何计算，它是一台通用计算机。刚才的程序就是个简单例子，只要有足够的规则，状态和纸带 可以创造任何东西——浏览器, 魔兽世界 任何东西！
当然 这样做效率很低，但理论上可行。所以图灵机是很强大的计算模型。事实上，就可计算和不可计算而言，没有计算机比图灵机更强大。和图灵机一样强大的，叫 "图灵完备"。每个现代计算系统 比如笔记本电脑，智能手机，甚至微波炉和恒温器内部的小电脑，都是"图灵完备"的。
03
停机问题
为了回答可判定性问题，他把图灵机用于一个有趣计算问题："停机问题"。简单说就是"给定图灵机描述和输入纸带，是否有算法可以确定机器会永远算下去还是到某一点会停机？我们知道输入 1 1 0，图灵机会停机，因为刚做过这个例子，它最后停机了。
但如果是更复杂的问题呢？有没有办法在不执行的情况，弄清会不会停机？一些程序可能要运行好几年，所以在运行前知道 会不会出结果很有用，否则就要一直等啊等，忧虑到底会不会出结果。当几十年后变老了，再按强制结束，好悲伤。
图灵通过一个巧妙逻辑矛盾证明了停机问题是无法解决的。我们来看看他的推理，想象有一个假想图灵机，输入：问题的描述 + 纸带的数据，输出 Yes 代表会"停机"，输出 No 代表不会。我要给这台机器一个有趣的名字叫 H， 来自"停机"的第一个字母。不用担心它具体怎么工作。假设这样的机器存在就好 ，毕竟重点是推论。
图灵推理说：如果有个程序， H 无法判断是否会"停机"，意味着"停机问题"无法解决。为了找到这样的程序，图灵用 H 设计了另一个图灵机，如果 H 说程序会"停机"，那么新机器会永远运行（即不会停机），如果 H 说程序会"停机"，那么新机器会永远运行（即不会停机）。如果 H 的结果为 No，代表不会停机，那么让新机器输出 No，然后"停机"。
实质上是一台和 H 输出相反的机器，如果程序不停机，就停机。如果程序停机，就永远运行下去。
我们还需要在机器前面加一个分离器，让机器只接收一个输入，这个输入既是程序，也是输入，我们把这台新机器叫 Bizzaro。
目前为止，这个机器不难理解，但接下来马上会变复杂，会有点难懂。如果把 bizzaro 的描述，作为本身的输入会怎样？意味着在问 H ，当 bizzaro 的输入是自己时会怎样？但如果 H 说 bizzaro 会停机，那么 bizzaro 会进入无限循环，因此不会停机。如果 H 说bizzaro不会停机，那么bizzaro会输出 No 然后停机，所以 H 不能正确判定停机问题。
因为没有答案，这是一个悖论，意味着"停机问题"不能用图灵机解决。
还记得刚刚说：图灵证明了图灵机可以实现任何计算，"停机问题"证明了，不是所有问题都能用计算解决。
下一节：讲讲图灵的生平
相关阅读：
京公网安备 11010502036488号