计算机先驱——艾伦·麦席森·图灵

Alan Mathison Turing，1912年6月23日－1954年6月7日
1931年图灵进入剑桥大学国王学院，毕业后到美国普林斯顿大学攻读博士学位
英国数学家、逻辑学家，被称为计算机科学之父，人工智能之父。

谜题

关于数学漏洞的问题，我给大家举个例子。剑桥有位数学家——伯特兰·罗素（Bertrand Russell）发现了一个数学漏洞。此前罗素的工作已经取得了巨大的成功——他证明了所有数学问题都可以还原为逻辑问题，也就是说，所有数学发现都可以用逻辑表达式重新写出来。 这项工作是伟大的，因为它有助于我们了解数学赖以建立的所有基本真理。但是后来，罗素发现了一个问题。他发现了一个悖论——也就是看起来既正确又不正确的论断。数学家经常寻找悖论，因为你如果觉得某件事情既正确又不正确，那么你的想法肯定有漏洞。所以，通过这种方法可以将很多想法证伪。相比之下，罗素悖论的性质要严重许多，因为它似乎预示着，整个数学体系是有漏洞的。
罗素悖论给我们出的难题是： 假设有一个集合A，它的所有子集都具有一个共同的性质P——它们不包含自身。
问题是：集合A是否包含自身？ 首先，若A包含自身，则A是A的子集，那么A具有性质P，由性质P知A不包含A；其次，若A不包含A，也就是说A具有性质P，而A是由所有具有性质P的集合组成的，所以A包含A。就像理发师悖论一样，唯一说得通的解法是，集合A既包含自身，又不包含自身。这在逻辑上是不可能的。
罗素悖论的提出之所以让数学家如临大敌，是因为它预示着数学的理论基础存在漏洞。几个世纪以来，数学思想和证明无不建立在一系列的基本真理之上。连加法和减法的运算法则都是运用集合和逻辑学加以证明的。但是罗素悖论表明，任何数学证明都不再可信。

罗素悖论还只是这一切的开端。1931年，在图灵攻读高级课程的四年前，有位数学家一劳永逸地证明了数学体系必定是不完备的。他的名 字叫库尔特·哥德尔（Kurt Gödel）。
哥德尔的第一条定理可以通过类似的方式表述出来：G＝“本命题不可以由理论T证明。”
如果命题G事实上可以由理论T证明，则理论T中存在一个自相矛盾的定理G，既然有自相矛盾的地方，那么理论T就是不完备的。也就是说，T要是完备的理论，就不可以证明G，但是这样一来，T就有证明不了的命题，也称不上是完备的理论了。于是，G所指的内容就是真的：G既无法得到证明，但又是真命题。由此可见，有些事物不管能否得到证明，都可以为真。

图灵在学校也学到了一个与此相关的前沿思想。这是由德国数学家大卫·希尔伯特（DavidHilbert）在1928年提出的挑战。这项挑战称为“判定问题”（Entscheidungs problem）。希尔伯特想知道的是，一个命题的真假能否自动判定。他的问题是，对于给定的数学语言，有没有什么方法或者程序可以让机器判定某件事情的真假，并将结果显示出来。
虽然这听起来颇为实用，但真正的挑战在于：这种自动化的方法或机器是否有可能存在？自动判定简单的句子似乎并不是遥不可及的事情，但如果是用复杂的数学语言写成的高难度句子，是否仍有可能加以判定？这种万能的真理说明者是否真有可能存在？

永不停机的图灵机

当时没有任何机器能做到这一点，于是图灵构想了一台能做到这一点的机器。他想象的是一台理论计算机。一台能从纸带上读取信息的机器。根据即时读取的指令，机器可以将纸带左移、右移，或在纸带上读取信息、输出结果。虽然这台奇怪的新机器终究只是纸上谈兵的假想机，但是这已经足够了，因为图灵只是想从理论上解决希尔伯特提出的问题而已。或许颇具讽刺意味的是，图灵虽然提出了关于通用计算机的思想，但却并不急着证明他的机器可以解决判定问题。相反，他想证明判定问题不可能得到解决，进而说明有些问题在数学上根本不可判定。
为了做到这一点，图灵首先假想他的小计算机正在根据纸带上的信号执行一个运算，接着他提出了一个问题：有没有什么方法可以判断这 台机器究竟是会陷入死循环，不停地计算下去；还是会停止计算，给出结果呢？

图灵认为，要想判断他的机器会不会停机，那就需要再构造一台图灵机，以对第一台机器进行检测，因为他知道，他假想的机器在理论上 可以进行任何数学运算。于是他假想出第二台图灵机，如果检测到第一台图灵机永不停机，那么第二台机器就会停机，然后输出“不停机”；如 果检测到第一台图灵机停了机，那么第二台机器就会一直运转下去。
现在，脑筋急转弯的地方来了。假如第二台机器反观自身，判断自己会不会停止计算，那会发生什么情况？图灵对此进行了设想，他突然发现了一个悖论：如果机器检测到自己会永不停机，那么它就会停机，然后输出“不停机”；如果机器检测到自己停了机，那么它就会一直运转下去。这在逻辑上是不可能的，由此证明，有些图灵机是不可判定的——我们永远也无法判断它们会不会停机。

顺便说一下，图灵当时设计这个图灵机，完全只是为了辅助他证明这个问题而已，这个机器是假想的，不存在的就像画一条辅助线。可是后来他又发现，虽然这个机器不能解决所有的问题，但确实能够解决很多问题，而且真的是可以造出来的。于是…… 图灵就成为了“计算机科学之父”。

P是否等于NP？

P和NP指的是两种类型的问题，它们的计算复杂度各不相同。P类问题可以通过多项式时间算法解决。换句话说，凡是可以用O（n^x）算法解决的问题都是P类问题，不管这里的x是什么。排序问题就是典型的P类问题。就算是最好的排序算法，它的时间复杂度在最坏的情况下也是O（n^2），符合多项式关系，因此排序问题属于P类问题。对于NP类问题，我们可以在多项式时间内检验候选解是否正确，但是求解所需要的时间却会漫长许多——而且往往是指数时间。
在已知量较小的情况下，所有这些问题乍看之下都很好解决，但是，一旦已知量的数量级增大，比如配送车穿行的城市增加到一百个、装箱的行李数量增加到五百个、硬币的数量限制增加到一百个，那么求解所需要的时间就会呈指数式增长。因此，P是否等于NP的问题实际上是在问：难度很大的NP类问题究竟能否用多项式算法求解？我们现在采用的算法是不是太愚蠢了，就像慢速排序那样？能不能找到像快速排序这种聪明的解法，让原本很难的问题一下子迎刃而解？

显然，NP类问题很难解决，但早在1936年，图灵对如此艰涩的难题就已经有了自己的思考方法。思考NP类问题的方法之一，就是构造一台特殊的图灵机，称为非确定型图灵机（non-deterministic Turing Machine）。如果我们可以制造出这样的机器，就可以让它在多项式时间内运行NP类问题。之所以称之为非确定型，就是因为我们无法预测它的运作方式，但它总能找到最快的方法解决问题。
试想你在干草堆里寻找一根针。你立马就能分辨出自己看到的是一棵干草还是一根针，但是从哪里寻找却是一个很大的问题。你有很大的选择空间，但问题是：“怎样做出选择才能让我找到解法？”
非确定型图灵机的道理与之大同小异。它的问题是：“是否存在某种特定的指令，可以使我成功求解？”如果这样的指令存在，那么它就会惊呼“太好了！”然后遵照指令，在最快的时间内找到解法。如果这样的指令不存在，那么它就会唏嘘“太可惜了”，然后停止运转。
至于这类聪明的图灵机是如何判断出解题方法的，这一点在某种程度上讲还是个迷。对此，人们设想了两种情况。第一，答案已经摆在那里了。这就好比你有一块魔镜，它无所不知，每次都会告诉你：这是最好的选择。第二，可以采用某种平行或并行操作，也就是说，这类非确定型图灵机所做的，其实就是同时运行所有可能的选择。 这些奇怪的思想是由图灵等业界先驱同时提出的，它们历经发展演进，为一个新的理论研究领域提供了肥沃的土壤，这个研究领域叫做可计算性理论（有时又称为递归论）。

总结

可计算性理论以及图灵机

图灵先知先觉，在电子计算机远未问世之前，他已经想到所谓“可计算性”的问题。物理学家阿基米得曾宣称:“给我足够长的杠杆和一个支点，我就能撬动地球。”类似的问题是，数学上的某些计算问题，是不是只要给数学家足够长的时间，就能够通过“有限次”的简单而机械的演算步骤而得到最终答案呢？这就是所谓“可计算性”问题，一个必须在理论上做出解释的数学难题。

“图灵机”是一个虚拟的“计算机”，完全忽略硬件状态，考虑的焦点是逻辑结构。图灵在他那篇著名的文章里，还进一步设计出被人们称为“通用图灵机”的模型，它可以模拟其他任何一台解决某个特定数学问题的“图灵机”的工作状态。他甚至还想象在带子上存储数据和程序。“通用图灵机”实际上就是现代通用计算机的最原始的模型。
不过图灵在提出图灵机构想之后，又发现了新问题，有些问题图灵机是无法计算的。比如定义模糊的问题，如“人生有何意义”，或者缺乏数据的问题，“明天3D中奖号是多少”，其答案当然是无法计算出来的。但也有一些定义完美的计算问题，它们亦是不可解的，这类问题称为不可计算问题。
不可计算的问题在践中几乎碰不到，事实上，很难找到这样的例子，既不可计算但又有人向计算的明确定义的问题。一个罕见的问题是所谓的停机问题。

图灵机的意义

图灵提出图灵机的模型并不是为了给出计算机的设计，它的意义我认为有如下几点：
1.它证明了通用计算理论，肯定了计算机实现的可能性，同时它给出了计算机应有的主要架构；
2.图灵机模型引入了读写与算法与程序语言的概念，极大的突破了过去的计算机器的设计理念；
3.图灵机模型理论是计算学科最核心的理论，因为计算机的极限计算能力就是通用图灵机的计算能力，很多问题可以转化到图灵机这个简单的模型来考虑。

对图灵机给出如此高的评价并不是高估，因为从它的设计与运行中，我们可以看到其中蕴涵的很深邃的思想。
通用图灵机等于向我们展示这样一个过程：程序和其输入可以先保存到存储带上，图灵机就按程序一步一步运行直到给出结果，结果也保存在存储带上。
另外，我们可以隐约看到现代计算机主要构成（其实就是冯诺依曼理论的主要构成），存储器（相当于存储带），中央处理器（控制器及其状态，并且其字母表可以仅有0和1两个符号），IO系统（相当于存储带的预先输入）；