1926年，英国由于煤矿劳资纠纷问题而爆发总罢工 ，汽车和火车全线停运。当时正逢学校开学，14岁的艾伦·图灵要去的是一所精英寄宿学校：位于多塞特郡的谢伯恩男子中学。但是他住在南安普敦，离学校大概有60英里远（约合96.6公里）。很多学生这时候都会干脆在家休息，等着为期十天的罢工结束以后再去上学，这样就可以享受更长的假期了。但图灵不是这种人。他毅然骑上自行车，往学校奔去。他骑了整整两天的时间，中途只在一家小旅馆歇了歇脚。就这样，年轻的图灵准时赶到了新学校。

图灵之所以养成了独立的性格，或许是因为他和哥哥约翰并不在父母身边长大。图灵夫妇都住在印度，但他们认为，孩子应该在英国接受教育。于是，他们把孩子留在了英国，和朋友同住。直到1926年，小图灵的父亲才退休回到英国——他回来的时候，小图灵正骑着自行车风风火火地往学校赶。

这是一个令人惊叹的开端，但是艾伦·图灵在新学校的成绩并不太好——以前也从来没有好过。他的字迹潦草，英语写作奇差。英语老师给出了这样的评语：“我可以原谅他的写作，但我这辈子都没见过写作水平这么差的。他的作文一向用词不当、粗制滥造、字迹潦草，不管写多少篇都是这样，我已经尽了最大的努力容忍他的劣质作文了……”拉丁语老师的评价也没有好到哪里去：“他成绩落后，总是犯一些滑稽可笑的错误。”

之所以会出现这样的问题，原因是图灵并不在乎课内成绩，而是把时间都花在了自己感兴趣的学问上。他独自开展化学实验，每次遇到数学难题都自己想办法解决。凭借独创的解题方法，他几乎包揽了学校颁发的所有数学奖项。任课老师不知道的是，图灵甚至已经开始从祖父给他的书中学习爱因斯坦的相对论思想和量子力学的最新理论。然而，他的才能并没有得到校长的赏识，校长说：“图灵要是想继续留在公学（英国的私立精英学校），就得让自己变得富有教养。如果他只是想当一名科学专家，那么他在公学上学简直是浪费时间。”

从小时候开始，图灵一直将一头深色的短发梳成标志性的左偏分。他的声音并没有随着年龄的增长而低沉多少，口吃的毛病也总是让周围的人误以为他不庄重。据图灵的母亲回忆，他在学校里没什么朋友，看起来日子也过得并不快乐。有位同学曾经给他画了张素描，画中的图灵正出神地看着曲棍球场中央生长的一簇雏菊——当时球场上正在比赛。不过，图灵不仅是个梦想家，还是个运动健将。他经常练跑步，长大后还成了训练有素的马拉松运动员。有一次，他在宿舍的楼梯井里自制了一个傅科摆 的复制品，来显示地球的自传。这件事终于使他在学校受到了一些重视。

图灵升上男子寄宿学校的预科班后，遇到了人生中的第一个重要的朋友——克里斯托弗·莫科姆（Christopher Morcom）。莫科姆也是一名天资聪颖的学生。两人经常用化学和数学难题互相挑战。在莫科姆的影响下，图灵申请了剑桥大学三一学院的奖学金。他们一起去面试，结果克里斯托弗顺利通过，而图灵不幸失败。没过多久，悲剧发生了。克里斯托弗患上了牛结核病——这种结核病，可以通过病牛未经巴氏消毒的牛奶传播给人。他没能战胜病魔，英年早逝。18岁的图灵受到了沉重的打击。痛失挚友的创伤使他开始深入思考生命与物理学的关系——他在余生的大部分时间里也在研究这些学科。为了纪念挚友，他下定决心继续努力，实现两人共同的志愿。因此，到了第二年，他又一次参加了考试，申请了剑桥大学国王学院 。这一次，他成功考取了自己理想的学校。

考上大学后，图灵突然发现自己来到了一个全新的世界。在剑桥，他可以自由探索自己的想法，充分施展打破常规的天性。他开始参与社交，练习划船，同时继续坚持长跑。在学术上，他继续深入钻研量子力学、数学和逻辑学。在道德科学俱乐部（Moral Science Club，剑桥的一个哲学讨论组），他读到了一篇关于数学和逻辑学的论文。同时期的俱乐部成员概括了图灵在这个问题上的观点：“他认为，不能只从逻辑的角度看数学；一个数学命题可以有多种解读方法，逻辑解读只是其中的一种。”换句话说，图灵认为，数学可能比逻辑学更加博大精深。

1934年，图灵以优异的成绩毕业，并继续在剑桥深造，学习数学基础的高级课程。他写了一篇奖学金论文，证明了统计学的中心极限定理 ——后来发现这个定理在很多年前已经被证明过了。这种事情对于图灵来说已经是家常便饭，而且他这么做是有充分理由的。很多年后，他的同事詹姆斯·威尔金森 （James Wilkinson）道破了其中的缘由。“图灵有个强烈的嗜好，他喜欢从最基本的公理出发来推导结论，他通常只审一遍题，就开始自己想办法解决，完全不参考前人的解法。显然，正是因为养成了这样的习惯，他的解法才那么具有独创性，可以说是自成风格。这让我想起了贝多芬说过的一句名言。当时有人问贝多芬听没听过莫扎特的曲子，毕竟莫扎特正备受关注。贝多芬说，‘没有，我也不应该去听，以免受到影响，扼杀自己的创造力。’”

“图灵把这个信条贯彻到了极致。老实说，我一开始对他的做法还挺恼火的。每次他给我布置一个任务，我完成以后，他都不肯赏脸看一看我的解法，而是会自己先解一遍；只有自己先初步尝试一遍之后，才会看我的解法。我很快就看到了他这样做的好处。首先，他如果不亲自尝试，是不会轻易接受别人的想法的，不过更重要的是，他经常会想出一些具有独创性的方法。这些方法我可能想都没有想过，而且他要是一开始就看我的解法，也不一定想得出来。”

探索不可能解开的谜题

图灵在剑桥大学修读高级课程期间接触到了一个课题，以此为契机，他将向全世界展示自己的天才。这个课题非常适合图灵，因为它宏大而重要，直击数学的核心，而且尚未被人解决。

开课老师是剑桥大学的著名数学家马克斯·纽曼（Max Newman）（后来他也成了图灵的挚友和同事）。课程的重点在于探索数学的极限——是不是一切事物、以及任何事物在数学上都是可证明、乃至可计算的？这些令人费解的想法新颖独特，悬而未决，而且令人振奋。数学被认为是宇宙的形式语言 ——我们通过这种方式描述万事万物，计算将来会发生的事情。如果没有数学，那么科学、工程学和经济学根本不可能存在。数学上的漏洞一旦被发现，将在很大程度上决定未来哪些事物可以计算、哪些不可以计算。这些想法很快就激发了图灵的想象。

关于数学漏洞的问题，我给大家举个例子。34年前，剑桥有位数学家——伯特兰·罗素（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既无法得到证明，但又是真命题。由此可见，有些事物不管能否得到证明，都可以为真。

这个脑筋急转弯游戏产生了巨大的影响。人们发现，任何事情都无法通过数学加以证明。有些真理则根本无法证实。

这样的结果是毁灭性的。要知道，千百年来，一代又一代数学家孜孜不倦地投身研究工作，就为了建立一个全面而完备的数学体系，在这个体系中，从最基础的公理到最高级、最复杂的证明都可以确凿无误地加以证实。但是如今，哥德尔不完备定理表明，数学家的努力永远没有成功的希望，一个全面而完备的数学体系永远也无法创立。无论数学的理论基础有多么牢固，总会有一些真理永远无法证实。

图灵在学校也学到了一个与此相关的前沿思想。这是由德国数学家大卫·希尔伯特（David Hilbert）在1928年提出的挑战。这项挑战称为“判定问题”（Entscheidungsproblem）。希尔伯特想知道的是，一个命题的真假能否自动判定。他的问题是，对于给定的数学语言，有没有什么方法或者程序可以让机器判定某件事情的真假，并将结果显示出来。这样一来，你就可以告诉这台神秘的机器，你输入的语言符合逻辑，让它判断下面这句话是正确还是错误：“如果所有的姐妹都是女性，而莎拉是你的姐妹，那么莎拉是男性。于是机器就会稍加思考，然后输出结果“错误”。或者你可以告诉机器，你输入的语言是算术语言，让它判断下面这句话是正确还是错误：“任何大于1的整数都可以通过质数相乘求得。”于是机器又会思考一番，输出结果“正确”。

虽然这听起来颇为实用，但真正的挑战在于：这种自动化的方法或机器是否有可能存在？自动判定简单的句子似乎并不是遥不可及的事情，但如果是用复杂的数学语言写成的高难度句子，是否仍有可能加以判定？这种万能的真理说明者是否真有可能存在？

永不停机的图灵机

图灵把接下来几个月的时间都扑在了这个问题上。年仅23岁的他或许资历尚浅，但他有一颗极富创造力的头脑，很快就想出了一些绝妙的点子。他所遇到的第一个问题，就是如何构想这个神秘的进程或机器。那个时候，电子学还没有创立，世界上最复杂的电气系统是前不久才问世的自动电话交换机——它们体型庞大，足以占满一座宽敞的大厅。当时的机器只能做一件事情，那就是它们被设计出来做的事情。但是希尔伯特提出的挑战是制造一台万能机，这台机器必须通晓任何数学语言，能够看懂人们用数学语言表述出来的任何命题。要做到这一点，它必须能够按照任何顺序进行任何可能的数学运算，从而给操作者留出充分的余地改变问题，改编机器的程序。

当时没有任何机器能做到这一点，于是图灵构想了一台能做到这一点的机器。他想象的是一台理论计算机。

在1935年，如果你去翻阅词典，查找计算机的定义，就会查到这样的解释：“执行计算工作的人”。年轻的艾伦·图灵所构想出来的机器可以将人们以往用纸笔进行的运算过程全部自动化。这台机器运作起来就像一个玩家在玩棋盘游戏——比如“大富翁”。它设有内存，而内存这个概念放到大富翁游戏棋中，就相当于棋子的位置、棋盘上的房子和玩家的资产。机器可以进入不同的运行状态，就像游戏当中会出现不同的场景。它的状态可以发生改变，好比玩家按照特定的规则推动游戏的进展。它需要来自外部的指令，遵守特定的规则，以改变运行状态，好比玩家掷出骰子以后，如果走到标有“入狱”的棋格，就得把棋子送进“监狱”。但是，与棋盘游戏不同的是，图灵机遵守的规则可以改变。事实上，规则可以由操作者输入，并储存到内存中（这就好比我们在棋盘上写下新的规则）。不仅如此，随着机器运行状态的改变，它所遵循的规则还可以进一步发生改变。（好比一个棋格上原本写着“免费停车场”，后来被改成“走进这个格子你就输了”）。在游戏规则会发生改变的情况下玩棋盘游戏，显然是一个高难度的挑战！但是试想一下，如果可以改变规则，那么整个游戏的性质都有可能发生改变，比如大富翁可以变成蛇梯棋，国际象棋可以变成西洋跳棋。

当然，图灵所指的并不是棋盘游戏。他想象的不是棋盘，而是一台能从纸带上读取信息的机器。根据即时读取的指令，机器可以将纸带左移、右移，或在纸带上读取信息、输出结果。不过，不管我们打什么样的比方来理解图灵机的运行机制，它的能力是始终如一的。图灵机是一台理论计算机。由于它可以完成任何可能的数学运算，现代计算机能做的事情都难不倒它（只不过它的运算速度要迟缓许多）。

虽然这台奇怪的新机器终究只是纸上谈兵的假想机，但是这已经足够了，因为图灵只是想从理论上解决希尔伯特提出的问题而已。或许颇具讽刺意味的是，图灵虽然提出了关于通用计算机的思想，但却并不急着证明他的机器可以解决判定问题。相反，他想证明判定问题不可能得到解决，进而说明有些问题在数学上根本不可判定。

为了做到这一点，图灵首先假想他的小计算机正在根据纸带上的信号执行一个运算，接着他提出了一个问题：有没有什么方法可以判断这台机器究竟是会陷入死循环，不停地计算下去；还是会停止计算，给出结果呢？看起来死循环的可能性很大，方法很简单，比方说在纸带A点上写上“移动到B点”，在B点上则写上“移动到A点”。

这个问题放到今天也很有现实意义，因为计算机一旦陷入死循环，或许就会“死机”，什么事情也做不了，这是我们不希望看到的。好比我们在自动取款机上输入PIN码（个人识别密码）以后，机器应该吐钱出来，而不是一动不动，什么反应也没有！

图灵认为，要想判断他的机器会不会停机，那就需要再构造一台图灵机，以对第一台机器进行检测，因为他知道，他假想的机器在理论上可以进行任何数学运算。于是他假想出第二台图灵机，如果检测到第一台图灵机永不停机，那么第二台机器就会停机，然后输出“不停机”；如果检测到第一台图灵机停了机，那么第二台机器就会一直运转下去。

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

尽管这样说或许令人费解、甚至不可思议，但是不可判定或不可计算的问题的确大量存在——自此之后，这样的事实一直让计算机程序员备受困扰。图灵的研究结果表明，有些数学问题是计算机无法解决的，这与计算机的运算能力、运算速度和内存容量无关。

1936年，正当年轻的图灵准备将这个振奋人心的成果公诸于世时，他偶然读到了美国数学家阿隆佐·邱奇（Alonzo Church）前不久发表的论文。那时候，全世界有好多数学家正在着手解决希尔伯特的判定问题。其中有的数学家——比如哥德尔——已经开始有了重要的研究成果。邱奇采用的方法与图灵截然不同，他需要创立新的数学概念和语言，以表述有关函数和演算过程的思想。他使用了自己创立的新语言——称为λ演算，并在哥德尔的基础上扩展了研究范围。研究结果表明，没有任何通用的算法可以判定任意两个λ表达式是否相等。也就是说，有些事情永远无法用数学方法加以判定——要想解决判定问题是不可能的。邱奇就这样率先攻克了希尔伯特挑战，他发表研究成果的时间只比图灵早了几个星期。

接下来几年里，还有其他描述算法的理论被相继提出，但它们都是等价的。邱奇的λ演算是经典的理论，它已成为计算机科学的宝贵工具，可用于对软件问题进行形式证明 。时至今日，它的地位依然举足轻重。不过，图灵机显然是概念方面的赢家。或许正是因为简洁易懂，图灵的计算机思想已成为理论计算机科学的基础。时至今日，连“可计算性”的定义都是根据他的思想界定出来的。“邱奇-图灵论题”（Church-Turing thesis）得到了广泛接受，该论题认为，任何可计算的问题都可以由图灵机计算。

图灵的贡献

1936年，由于志同道合，图灵决定去美国普林斯顿大学投奔邱奇，他在那里师从邱奇，完成了博士学业。

阿隆佐·邱奇自己的经历就带有传奇色彩。他在高中时由于气枪事故，导致一只眼睛失明，后来又因为这只眼睛失明而不小心被有轨电车撞倒，因缘际会，与照看他的护士坠入爱河，步入婚姻的殿堂。邱奇平时为人彬彬有礼，衣着干净整洁，宗教信仰坚定不移，有一些出了名的怪癖，喜欢阅读和收藏科幻小说，如果发现书中有错误，他会在目录页用铅笔修改，或者致信作者予以纠正。每次讲座开始之前，他都会按部就班地把黑板擦得纤尘不染，擦拭次数非得是偶数，而且一般都要用到肥皂和水。擦完黑板后，他会耐心地等待水迹风干，要不然不会开讲。每次开讲都是长篇大论，好像在看着书稿直接念一样。如果被人打断，他会很不自然地停下来。平时说话很少不用逻辑论证。有传言说，邱奇连吃早饭的方式都很有逻辑：“先把牛奶倒进空碗里，放适量的糖，用早餐勺搅拌均匀，然后放一两勺麦片。吃完这点麦片后，再接着放一两勺，边吃边放。这样一来，糖就会在牛奶中充分溶解，分布均匀，而且麦片也不会泡得太软。”

图灵从来没有变得像邱奇那么爱干净，不过他也培养了一些高度逻辑化的习惯，而且这些习惯有时显得很古怪。博士毕业回国后，图灵喜欢戴着防毒面罩骑车，以预防花粉症。如果他发现自行车经常在他踩14圈以后掉链子，他就会每踩完13圈以后下车调整链子。

1938年，图灵回国后不久，便受到政府代码及加密学校 （Government Code and Cypher School）的邀请，协助军方破解德国的著名密码系统——“恩尼格玛” （Enigma）。1939年英国宣战后，图灵开始在这家位于布莱切利公园的密码破译机构全职工作。他很喜欢这份工作，因为它充满挑战，而且工作环境又好。1940年，他发明了一台破译机——名为“炸弹机”（Bombe，得名于波兰的一台破译机），成功破解了德国空军传递的所有“恩尼格玛”加密情报。到了1941年年中，德国海军的“恩尼格玛”加密情报也被全部破译。1942年至1943年3月，图灵在美国协助破译工作；尽管德军升级了密码，但事实证明，图灵的思想又一次成为了最得力的破译工具。

据估计，图灵的贡献使密码破译工作缩短了两年。这份功劳可谓功德无量，要知道，战争期间每年就有1,100万人死亡。据说温斯顿·丘吉尔曾盛赞图灵，说他的工作为二战的胜利做出了最杰出的个人贡献。对于一位性格略有些古怪的极客来说，这已经是很高的赞誉了！图灵因为二战时期的杰出功劳获得了英王授予的不列颠帝国勋章（OBE），但是由于情报工作的保密性，他的功劳在接下来的三十年里一直不为人知。

二战结束后，图灵（如图1）继续发挥自己的才思，开展富有开创性的研究工作。他构想了世界上最早的计算机之一——自动计算机（Automatic Computing Engine，简称ACE）。当他知道恩师马克斯·纽曼当上曼彻斯特大学（Manchester University）教授后，自己也进入了曼彻斯特大学，担任讲师的工作。任教期间，他一方面继续开展数学研究工作，另一方面扩展了兴趣范围，研究了神经科学、个体发生学 和量子理论。图灵是人工智能研究领域的先驱之一（我们会在后面的章节提到他的好几个思想）。1951年，他因为图灵机的研究工作而当选为伦敦皇家学会（Royal Society of London）的成员。他的大学同事并不知道，他在任教期间依然供职于英国通信总部（GCHQ，相当于国家安全局），继续参与密码破译的工作，直到冷战爆发。

1952年，图灵向警方报告了一起入室盗窃案。他承认，行窃的人正是他以前的同性伴侣的朋友。但是同性恋在当时是非法的，因此图灵被控以严重猥亵罪而遭到起诉。审讯期间，他的老朋友马克斯·纽曼为他出庭作证，但是于事无补。图灵不幸被定罪，他的选择只有两个，要么坐牢，要么接受“化学阉割”——注射女性荷尔蒙（雌激素）。他选择了注射雌激素，为此不得不遭受乳房发育等药物副作用的伤害。他不再具备参与保密工作的资格，不能再为英国政府通信总局工作。他的一举一动——无论是外出度假，还是与外国科学家开展合作——都在国安人员的密切监视之下。

图灵继续开展研究，发表了更多关于个体发生学、量子理论和相对论的论文。他四处旅行，游历了巴黎、雅典和科孚岛（Corfu，位于希腊西北部，爱奥尼亚群岛之一）。但他并不快乐。1954年，图灵被发现死在家中，身边放着咬了一口的苹果。此前他一直在做电解实验，身上可能残留了化学物质，而苹果表面检测出了氰化钾。图灵的母亲和他在通信总部的几名同事认为，这是一起事故。警方的调查结论称，他的死因是自杀。

图灵的伟大贡献从未被世人遗忘。他被大多数学术界人士尊为计算机科学之父。但是公众对他的看法只能用莫衷一是来形容。1998年，图灵故居的门边挂上了蓝牌（Blue Plaque，向名人故居发放的一种证明标志），时值这位伟人的86周年诞辰。当时，罗杰·彭罗斯爵士 （Roger Penrose）写道：“开创计算机革命的中心人物是艾伦·图灵，他杰出的创见和视野使这一切成为了可能。变革始于20世纪30年代，尽管我们现在难以预见计算机革命的极限究竟何在，但是图灵本人指出了这种理论局限性的存在。”2001年，曼彻斯特的萨克维尔公园（Sackville Park）树起了一座纪念雕像。雕像中的图灵坐在长凳上，手里拿着一个苹果。

如今，英国国家计算博物馆（National Museum of Computing）就坐落在布莱切利公园。管内设施完全对公众开放，其中包括图灵的办公小屋。图灵的马克杯至今依然拴在小屋的暖气片上（谁也不知道他为什么喜欢把杯子拴在上面）。最近，国家计算博物馆获得了珍贵的图灵论文手稿，作为馆藏展品。苏·布莱克是一名计算机科学家，她经常代表馆方在电视、电台和社交媒体上发起宣传活动。通过布莱克及其他热心人士的努力，国家计算博物馆得到了足够的宣传和谷歌等企业的赞助，可以保持对公众开放。

一说起图灵，布莱克就激动万分。“他饱受迫害，遭到起诉，被迫在坐牢和化学阉割之间做出选择——结果不得已选择了化学阉割……这都是些何等非人的对待啊！他是上个世纪最伟大的人物之一，但却沦落得那么凄惨。”

“我们无法让时光倒流，改变图灵的境遇，”布莱克表示，“但是我们可以纪念他取得的伟大成就。希望他的故事可以激励更多的人勇于奋进，即便他们一开始默默无闻。”

2009年，由于科学家和公众的广泛支持，一项要求政府道歉的请愿活动取得了成功。首相戈登·布朗（Gordon Brown）发表了一篇情真意切的致歉信，信的结尾写道：“……我谨代表英国政府、以及所有因图灵的工作而自由生活的人，对他说：‘我们很抱歉，你本应该得到更好的对待’。”

复杂即是简单

通用图灵机（Universal Turing Machine）已成为世界上所有电子计算机的理论蓝图。它反映了计算机的行为模式，指导着人们设计和制造真正的计算机。正因为有了这个理论基础，我们清楚地知道，任何一台计算机都可以模拟其他计算机的行为（只要有充足的时间和内存）。这一点甚至在第一台电子计算机问世之前就已经为人所知。

图灵机仍然是理解可计算和不可计算问题的最佳理论工具之一。有些计算机科学家认为，这两种类型的事物或许有助于我们深入了解宇宙的本质。伦敦大学的马克·赫布斯特（Mark Herbster）就是这样一位研究人员。“我认为可计算性理论比很多物理定律更有说服力，”他表示，“你可以研究可计算事物和不可计算事物的基础。它们是现实世界的基本范畴。我认为它们是我们的宇宙乃至一切可能存在的宇宙所固有的事物。”

可计算理论还有一些非常实际的应用：比如计算完成某个运算需要的时间。即便有些运算过程在理论上是可能的，这也并不意味着我们制造的计算机具备与之匹配的运算能力。

理论计算机科学家罗宾·赫希（Robin Hirsch）研究了这些思想。“这个世界上存在三种类型的事物，”他说，“第一种在理论上可能做到，但却无法解决；第二种在实际上可能做到（因此在理论上也必定可能做到）；第三种在理论上可能做到，但在实际上却未必可能做到——虽然说是在理论上可能做到，但往往是比较匪夷所思的类型，即使宇宙的寿命终结也不一定能够完成，所以从实际角度讲，我们也解决不了。在计算机科学领域，大多数有趣的问题都属于这个范畴。”

这是一个非比寻常的思想。无论我们的技术发展到多么先进的地步，这三种类型的事物会一直存在。像图灵的停机问题这种无法判定的问题就属于第一个范畴。要想解决它们是不可能的，不管你使用的是什么样的计算机。第二种类型——也就是在实际上可能解决的问题，一般都很容易证明。比方说，文字处理器、电子制表软件、计算机游戏——这些东西显然可以制造出来，因此，用计算机运行它们肯定是有可能的。但是第三种类型的问题挑战着人类的极限，解决起来要困难许多。有时候这类问题或许看起来不切实际，但我们只是在尝试突破当前的极限，对它们进行运算。有些事情或许根本就不可能实现——我们或许永远也无法制造出内存足够大、运算速度足够快的计算机来解决这些问题，但是不试试怎么知道呢？我们不想把时间浪费在解决不可能解决的问题上，但我们很乐意花时间提高自己的能力，对难度极大的问题发起挑战。

问题的难度一般随着规模的大小而发生改变。假设你是一个较真的学校教师，非得让班里30名学生按照从矮到高的顺序排成一列横队，最矮的站在左边，最高的站在右边。为了告诉学生应该怎么站队，你需要拿着卷尺两个两个地比对他们的身高，每比对一次可能要花上一、两分钟的时间。你不想把一整天都搭进去，所以比对的次数越少越好。那么你需要比对多少次呢？

当然，这个问题的答案取决于学生一开始是怎么站队的。在理想情况下，如果他们刚好按照从矮到高的顺序排成了一列横队，那么你只需要做29次比对。（别忘了，你是一个较真的老师，需要一个个进行检查。）在一般情况下，如果你采用了聪明的排序方法，那么平均需要比对的次数大约为44次。在最坏的情况下，如果你不幸采用了比较愚蠢的方法，把每个学生都和其他学生比对了一遍，那么你需要比对的次数为30 × 29=870次。（如果每一次比对都花了一分钟的时间，那么整个过程下来，就需要耗费14.5个小时。）

在计算机科学领域，我们常用的词是“算法”，而不是“方法”。这个术语主要用于描述我们打算写入计算机程序的方法或过程，它给出了程序运行的所有步骤。因此，所谓排序算法，就是指为一系列事物排序的方法。插入排序是其中一种算法：先让一名学生出列，然后让另一名学生和他排好队。这样一来，班里的学生就分成了两个横队，其中一个是有序队列，另一个是无序队列。将无序队列中的学生逐一插入到有序队列当中的合适位置，直到所有的学生都排成了有序队列。这种算法并不是很快，但是行之有效。还有一种算法称为抢椅子（只不过不需要真的把椅子用上）：让所有学生都跑动起来，随机改变站队位置，然后喊停，看队列是否有序。如果有序，则大功告成。如果无序，则继续抢椅子，直到所有学生都站成有序队列。这是一个非常愚蠢的算法，因为在最坏的情况下，这样算下去可能会没完没了，学生可能永远也站不好队。

因此，一个愚蠢的算法可能会让你白白浪费很多时间。相比之下，一个高效的算法运行起来就会快捷很多。当然，所有排序算法的运行时间都取决于排序对象的数量，但是愚蠢的排序算法耗费的时间通常要比高效的算法漫长许多。显然，我们更愿意采用寻找高效的算法——也就是时间复杂度 较低的算法。

计算机科学家有一种通俗直观的方法来表述算法的时间复杂度。我们称之为“大O符号”（Big O notation，一种描述函数渐近行为的数学符号）。假设排序对象的数量为n（在上面所举的例子中，n的数值为30），如果完成排序的时间仅仅取决于n的数值，那么算法的时间复杂度为O(n)；如果你把每一个排序对象都与其他对象进行比较，那么算法的时间复杂度为O(n×(n-1))——在这里，我们一般会把常数项和低阶项忽略不计，因为当n的数值非常大时，低阶项和常数对结果的影响就会微乎其微，所以，O(n×(n-1))可以简化为O(n 2 )。

目前最佳的排序算法平均时间复杂度为O(n log n)，比O(n 2 )要好很多。你可以自己检验一下。最快的排序算法称为“快速排序”（Quicksort），它的平均时间复杂度为O(n log n)。有一个较慢的算法称为“冒泡排序”（Bubblesort），它的平均时间复杂度为O(n 2 )。假设每一次比对需要一分钟，如果排序对象为十个，那么快速排序需要十分钟左右，冒泡排序则需要一个半小时以上；如果排序对象为一百个，那么快速排序需要3小时20分钟左右，冒泡排序则需要将近一个星期；如果排序对象增加到一千个，那么快速排序需要两天的时间，冒泡排序则需要将近两年！

冒泡排序虽然听起来很糟糕，但它还不是最差的。如果我们采用时间复杂度为O(2n 2 )的“慢速排序”（Slowsort ）算法，那么得出的结果就真的会变得很吓人。算法的运行时间呈指数式的飙涨。排序对象只不过才十个，慢速排序算法就需要耗费2411,816,210,479,888,000,000,000年的时间——这个运行时间甚至达到了宇宙年龄的1,754,050亿倍。

就算我们把比对速度加快（或许得使用某种超级并行计算机），将比对时间从一分钟缩短到理论上可测量的最小值——一个普朗克时间（Planck time）（5.316 × 10–44秒），一旦排列对象超过30个，慢速算法的运行时间依然漫长得吓人。另一种提升速度的方法就是扩大内存——但是这样一来，空间复杂度 就会直线上升：到时候，运行慢速算法需要的内存量可能会比全宇宙物质的量还要多。

需要指出的是，算法之所以在理论计算机科学领域举足轻重，不仅仅是因为我们可以借此让软件运行得更高效，而且还因为它能够告诉我们，从实际角度看，哪些问题容易解决，而哪些问题难以攻克。排序是计算机能够解决的一个非常简单的问题，就算排序对象的数量级很大也是如此，因为我们能够设计出时间复杂度较小的算法，比如快速排序算法。但是对于有些问题，我们所能取得的最好成果，也就只有慢速排序那点程度了。

至少我们目前是这么认为的。

P是否等于NP？

2000年，美国商人兰顿·T·克雷（Landon T. Clay）公布了千禧年大奖难题（又称世界七大数学难题）。解开任何一道难题的人都可以获得一百万美元的奖金，这笔奖金将由克雷在美国马塞诸塞州剑桥市新开设的克雷数学研究所（Clay Mathematics Institute，简称CMI）颁发。十年过去了，只有一道难题被人攻克，解答者是俄罗斯圣彼得堡的数学家格里戈里·佩雷尔曼（Grigoriy Perelman）博士。尽管佩雷尔曼为他的研究领域做出了“无与伦比的巨大贡献”，他依然将一百万美元的奖金拒之门外（还有好几家久负盛名的机构想给他颁奖，也遭到拒绝）。尽管如此，学术界还是有不少人对解题拿奖心驰神往。

在尚未解决的六大难题中，有一道题或许是最简洁的。它的题干是：P是否等于NP？

P和NP指的是两种类型的问题，它们的计算复杂度各不相同。P类问题可以通过多项式时间 算法解决。换句话说，凡是可以用O(nx)算法解决的问题都是P类问题，不管这里的x是什么。排序问题就是典型的P类问题。就算是最好的排序算法，它的时间复杂度在最坏的情况下也是O(n2)，符合多项式关系，因此排序问题属于P类问题。

对于NP类问题，我们可以在多项式时间内检验候选解是否正确，但是求解所需要的时间却会漫长许多——而且往往是指数时间 。至于这段时间可以漫长到什么地步，大家看了上一节那个慢速排序的例子，想必已经很清楚了。

求解的时间比检验解法的时间还长，这听起来或许有些匪夷所思，但是大家只要思考一下下面这个问题，就会明白其中的道理了。假设你负责给无家可归的人提供福利住房。公寓楼里可以安排一百个人入住。社会福利局给了你一张长长的名单，上面成对地列出了一些彼此合不来的人，他们不能安排在同一栋楼里居住。申请入住的一共有四百号人，你该如何做出选择？

无论你对这个问题如何求解，都可以轻而易举地检验出解法是否正确。你唯一需要做的，就是选出一百个人，然后对照一下社会福利局给的名单，确保彼此合不来的人没有同时入选就可以了。但是，要选出这一百个人其实非常困难。从四百名申请者当中选出一百个人，这样的组合可以有很多种。在人类已知的宇宙中，原子的数量都没有这么多。因此，这个问题属于NP类问题。我们可以很快地检验出候选解是否正确，但要找到完美的解法比登天还难。

我们发现，日常生活中有很多例子都属于NP类问题。就拿大家都很熟悉的扫雷游戏来说吧，它的玩法就是一个NP类问题。再举几个例子，怎样计算配送车穿行于各个城市的最佳路径，同时尽量缩短车程？这是一个NP类问题；如果你有很多大小不同的行李，怎样装箱才能最大程度地节省空间？这也是一个NP类问题；如果你有一张清单上列出了所有需要完成的家务活，怎样才能在有限的时间里安排它们的先后顺序？这又是一个NP类问题；给出一个固定的金额，怎样才能凑够这笔钱，同时尽量少用硬币？就连这种事情也是NP类问题。在已知量较小的情况下，所有这些问题乍看之下都很好解决，但是，一旦已知量的数量级增大，比如配送车穿行的城市增加到一百个、装箱的行李数量增加到五百个、硬币的数量限制增加到一百个，那么求解所需要的时间就会呈指数式增长。

因此，P是否等于NP的问题实际上是在问：难度很大的NP类问题究竟能否用多项式算法求解？我们现在采用的算法是不是太愚蠢了，就像慢速排序那样？能不能找到像快速排序这种聪明的解法，让原本很难的问题一下子迎刃而解？

多年来，为数众多的计算机科学家一直在努力证明或者证伪P=NP。巧合的是，其中一名科学家恰好是我在伦敦大学学院的同事。我第一次见到他的时候，他还是个学生。他的名字叫丹尼尔·赫尔姆（Daniel Hulme）。

早在学生时代，丹尼尔就对P=NP问题产生了兴趣，他利用业余时间想出了一个聪明的算法。他把一般用于满足约束条件的方法用在了求解上，从而在多项式时间内解决了一些NP类问题。在这里，他主要研究的是布尔可满足性问题（Boolean Satisfiability，简称SAT），也就是所谓的“判定问题”，只不过是用逻辑运算符“与”、“或”、“非”构建出来的（相当于把电子电路转化为数学问题，我们在下一章还会提到）。布尔可满足性问题的一大应用就是电路验证。这里的判定问题或可表述为：是否任何一组输入都能让电路工作？或者说，是否存在一组特定的输入，使电路无法工作？

布尔可满足性问题属于NP困难问题（NP-hard）。也就是说，它们的难度不亚于NP类问题中最困难的范畴。同时，布尔可满足性问题也属于NP完全问题（NP-complete）。也就是说，只要你为这些问题找到了多项式时间解法，那么你就掌握了快速解决所有NP类问题的钥匙，因为所有NP类问题都可以归结为某种形式的布尔可满足性问题。如果丹尼尔的聪明算法能够在多项式时间内解决所有布尔可满足性问题，那么他就相当于证明了P=NP。

丹尼尔的故事非常引人入胜。“一开始，我的博士论文研究的课题是，如何通过计算机建模，分析熊蜂的视觉机制，”他说，“不过我喜欢在业余时间研究自己感兴趣的P=NP问题。我试图说服自己P不等于NP。这样做很傻，我知道。但是我喜欢给自己挑战！我得出了一些很有意思的结果，导师允许我把这一领域的研究工作继续开展下去，作为博士论文的课题。我想出了一些自己觉得比较高明的实用算法，它们的运算效果应该会比已有的算法更好。”

“我选了一些已经解决的布尔可满足性问题，用自己的算法解了一遍，发现它比很多已有的解法更好。很多其他算法无法解决的问题我都解决了。于是我找到导师，跟他说，‘老师您看，我想出了一个实用的多项式算法，它可以解决这些问题。您能不能帮我看看这个算法可不可行？’”

丹尼尔的导师伯纳德·巴克斯顿（Bernard Buxton）将这个问题交给了罗宾·赫希。赫希回忆道，“他觉得自己证明了P=NP，于是伯纳德让我帮忙看看。经过一番辩论，我还是发现了一些很难察觉的问题。丹尼尔并没有证明P=NP，他的算法并不一定适用于所有情况。但是丹尼尔不太相信我。”

这样的消息对于丹尼尔来说有些难以接受。“那时候，我发现自己的多项式解法不仅能解开一些比较重要的布尔可满足性问题，而且比很多已有的解法更快。我感到非常振奋，因为这个基本的多项式算法可以打败布尔可满足性问题的众多解法。我觉得这就是我们以后应该遵循的研究方向。”

罗宾不得不向丹尼尔证明他的算法并不是那么的天衣无缝。“我不得不构建一个病态 反例，这对我来说很难，但我还是想办法做到了。丹尼尔的算法虽然有局限性，但却是是很好的研究成果。它已经非常接近正确答案了，在布尔可满足性问题的所有解法中，我觉得它可以称得上是数一数二的。丹尼尔的研究工作很了不起。”

当然，这样的结果对于丹尼尔来说无疑是令人失望的，不过丹尼尔意识到自己的算法依然非常有用。“罗宾的例子表明，如果问题增多到一定的程度，我的算法就不适用了。也就是在这时候，我意识到自己建立了一个很好的预处理算法。只不过它不是P=NP问题的正解——真是太可惜了！”

丹尼尔由于他在N=NP问题上的研究成果而被授予了博士学位。毕业后，他在硅谷创立了一家公司，命名为Satalia（这个名称由两个单词组成，它们分别是SAT和alia。SAT代表布尔可满足性问题，alia是拉丁文单词，意为“不同”或“其他”）。Satalia在英国的分公司命名为“NP完全”（NP-Complete）。公司成立的宗旨，就是为数学界找出NP完全问题的高明解法。但是除了这些商业目标，丹尼尔依然对解开“P是否等于NP”这个的神秘谜题心驰神往。“我觉得人的大脑就像计算机，”他说，“人的大脑经过了漫长的进化，尽管未必达到了最优的状态，但说不定就能找到P=NP问题的正解，谁知道呢？或许问题的答案已经通过硬编码 写在大脑里了，只不过我们还没发现，总有一天我们会把它破解出来的。”

“我的个人理想就是赚足够的钱给自己买一间办公室，再在办公室里配上一块白板（白色的金属板材料制的书写平面），这样我就可以随心所欲地研究P=NP问题了。”

预言及其他复杂性问题

显然，NP类问题很难解决，但早在1936年，图灵对如此艰涩的难题就已经有了自己的思考方法。思考NP类问题的方法之一，就是构造一台特殊的图灵机，称为非确定型图灵机（non-deterministic Turing Machine）。如果我们可以制造出这样的机器，就可以让它在多项式时间内运行NP类问题。之所以称之为非确定型，就是因为我们无法预测它的运作方式，但它总能找到最快的方法解决问题。

试想你在干草堆里寻找一根针。你立马就能分辨出自己看到的是一棵干草还是一根针，但是从哪里寻找却是一个很大的问题。你有很大的选择空间，但问题是：“怎样做出选择才能让我找到解法？”

非确定型图灵机的道理与之大同小异。它的问题是：“是否存在某种特定的指令，可以使我成功求解？”如果这样的指令存在，那么它就会惊呼“太好了！”然后遵照指令，在最快的时间内找到解法。如果这样的指令不存在，那么它就会唏嘘“太可惜了”，然后停止运转。

至于这类聪明的图灵机是如何判断出解题方法的，这一点在某种程度上讲还是个迷。对此，人们设想了两种情况。第一，答案已经摆在那里了。这就好比你有一块魔镜，它无所不知，每次都会告诉你：这是最好的选择。第二，可以采用某种平行或并行操作，也就是说，这类非确定型图灵机所做的，其实就是同时运行所有可能的选择。

这些奇怪的思想是由图灵等业界先驱同时提出的，它们历经发展演进，为一个新的理论研究领域提供了肥沃的土壤，这个研究领域叫做可计算性理论（有时又称为递归论）。可计算性理论研究的是不可计算函数，研究人员致力于探索它们的不可计算性究竟达到了何种地步——或许有些函数比其他函数更难，尽管它们都不可计算。这些思想听起来或许有些异想天开，但是，有好些非常重要的研究成果可以转化为实际应用。其中有个例子就是莱斯定理（Rice's theorem）。莱斯定理的内容是，对于图灵机使用的特定语言，我们无法判定它是否具有非平凡性 。这句话放到编程语言上就是指，没有任何通用的方法可以判定关于语言的非平凡问题。简单说来，这意味着，要想写出能够完美调试其他程序的计算机程序，是不可能做到的事情。换言之，我们永远无法避免软件出现错误。

另一个重要的思想涉及到一个概念，称为字符串复杂性。在计算机科学中，字符串就是指由字母或数字组成的有限序列，比如“abcdefg123456hijklmnop7890”。它可以代表任何事物，比如一个英语句子、一幅图像，甚至一首曲子。一个字符串的复杂度可以通过“柯尔莫哥洛夫复杂性”（Kolmogorov complexity）来衡量。至于柯氏复杂性的界定依据是什么，想必读者朋友们已经猜到了——没错，那就是图灵机。在给定输入为w的情况下，如果图灵机M能够生成某个字符串，而且采用了最简洁、最紧凑、最高效的生成方法，那么该字符串的柯氏复杂性就是M与w的编码长度之和。也就是说，柯氏复杂性与字符串看起来有多复杂无关，而纯粹取决于生成字符串的难度。

分形 几何图形就是一个很好的例子。曼德勃罗集 （Mandelbrot set）是一个复杂到无以复加的分形几何图形，不管你怎么放大，都可以看到无穷无尽的细节图案。它们多姿多彩，美不胜收，有的像海岸线，有的像有机分子结构，还有的像星罗棋布的河流。但是，纵使曼德勃罗集的图案千变万化，它的本质就是一个点集，这个点集出自一个非常简洁的方程式：xt+1=xt2+c，所以它的柯氏复杂性非常低，也就是说，我们只需要很少的信息就可以生成曼德勃罗集。

至于柯氏复杂性会产生什么效果，你只要会用计算机，就一定不会陌生，只不过你自己可能还没有意识到这一点。你可以在计算机上任选几个文件，用zip之类的压缩软件将它们压缩，这时你就会发现它们的大小缩水了，而且有些文件的缩水幅度比其他文件大很多。精密复杂的图片压缩起来没有简单的图片缩水幅度大。这是因为解压缩程序需要足够的信息才能生成原始图片，按照定义，复杂的图片需要较多的信息才能生成。

至于文件可以压缩到多小的地步，这是有理论极限的。至于极限究竟何在，我们可以通过使用精巧的压缩程序，找到些许蛛丝马迹。但是，或许颇具讽刺意味的是，没有任何通用的函数可以计算任意字符串的柯氏复杂性。这样的函数是不可计算的。

就算我们算不出具体的极限值，也会希望文件的压缩幅度能够超越理论的极限，因此，有损压缩 软件应运而生。MP3就是一个典型的例子，它的压缩幅度超过了理论的极限，压缩过程中损失了一定的信息，因此，与未经压缩的原始CD文件相比，MP3文件播放起来有一定程度的失真。音乐文件在保存为压缩格式的过程中，只损失了人耳不易分辨的信息，但是如果将一首曲子的MP3版和CD版对照起来播放，你还是能听出其中的细微差别。同样的道理也适用于jpeg和ti格式的图片。职业摄影师往往会将图片保存为未经压缩的ti格式，因为保存为jpeg压缩格式会丢失一定的信息，从而使图片的质量受到些许影响。你要是仔细查看jpeg格式的图像，就会发现，有些细节部分似乎显得模糊不清。但是ti和jpeg文件在大小上差别太大，所以大多数人还是会选择jpeg文件。

理论前景

艾伦·图灵及其同时代的人为计算机科学的诞生奠定了理论基础，不仅如此，很多人认为，是他们开创了计算机科学本身。图灵的悲惨境遇和英年早逝并没有使他的成就埋没于历史的尘埃中，相反，他的思想生根发芽，成为了人类知识宝库中的参天巨树，昭示着计算机的力量和局限。

理论计算机科学可能有时候给人的感觉像是脑筋急转弯，但是它与人们的生活一直息息相关。随着计算机的迅速普及，图灵开创的可计算性理论和计算复杂度理论也变得日益重要。我们将在后面的章节中提到，互联网正成为沟通整个世界的信息网和关系网，在信息模式日益复杂的情况下，要想检索出自己所需要的信息，已变得非常困难。软件正变得日益精巧，这给软件的调试和兼容带来了很大的挑战。只要我们能更加透彻地理解计算的理论问题，我们在解决实际问题的过程中就会更加得心应手。“如今，我们需要处理的数据量极为庞大，解决理论问题是一件刻不容缓的事情，”赫希表示，“因此我们需要构建更多的计算模型，这样就能在相对较短的时间内处理更多的数据……或许这意味着，理论问题已经变得空前重要。”

“P是否等于NP”这个难题的存在，也给很多数学家带来了不懈研究的强大动力。马克·赫布斯特对它的重要性坚信不疑。“在当今时代，理论计算机科学领域最重要的思想，就是时间复杂度等级的构建及其研究，它们是解决P=NP问题的关键。P=NP问题是数学和计算机科学领域最重要的一大未解之谜。”

图灵要是在世，或许已经为我们解开了P=NP问题。不过，千禧年难题百万大奖依然有效，P=NP这道难关一旦被攻克，计算机的性能和效率必将提升一个台阶，届时，一场新的计算机革命必将势不可挡。 WqXY/EysFcbHyfm/nSTx8Qrq+/Q21Sep//roWDvSnaSjcdDU0AmX7znFmAM3/1+R