第5章 你会计算吗？(2)
图灵在学校也学到了一个与此相关的前沿思想。这是由德国数学家大卫·希尔伯特（David Hilbert）在1928年提出的挑战。这项挑战称为“判定问题”（Entscheidungs problem）。希尔伯特想知道的是，一个命题的真假能否自动判定。他的问题是，对于给定的数学语言，有没有什么方法或者程序可以让机器判定某件事情的真假，并将结果显示出来。这样一来，你就可以告诉这台神秘的机器，你输入的语言符合逻辑，让它判断下面这句话是正确还是错误：如果所有的姐妹都是女性，而莎拉是你的姐妹，那么莎拉是男性。于是机器就会稍加思考，然后输出结果“错误”。或者你可以告诉机器，你输入的语言是算术语言，让它判断下面这句话是正确还是错误：“任何大于1的整数都可以通过质数相乘求得。”于是机器又会思考一番，输出结果“正确”。
虽然这听起来颇为实用，但真正的挑战在于：这种自动化的方法或机器是否有可能存在？自动判定简单的句子似乎并不是遥不可及的事情，但如果是用复杂的数学语言写成的高难度句子，是否仍有可能加以判定？这种万能的真理说明者是否真有可能存在？
永不停机的图灵机
图灵把接下来几个月的时间都扑在了这个问题上。年仅23岁的他或许资历尚浅，但他有一颗极富创造力的头脑，很快就想出了一些绝妙的点子。他所遇到的第一个问题，就是如何构想这个神秘的进程或机器。那个时候，电子学还没有创立，世界上最复杂的电气系统是前不久才问世的自动电话交换机——它们体型庞大，足以占满一座宽敞的大厅。当时的机器只能做一件事情，那就是它们被设计出来做的事情。但是希尔伯特提出的挑战是制造一台万能机，这台机器必须通晓任何数学语言，能够看懂人们用数学语言表述出来的任何命题。要做到这一点，它必须能够按照任何顺序进行任何可能的数学运算，从而给操作者留出充分的余地改变问题，改编机器的程序。
当时没有任何机器能做到这一点，于是图灵构想了一台能做到这一点的机器。他想象的是一台理论计算机。
在1935年，如果你去翻阅词典，查找计算机的定义，就会查到这样的解释：“执行计算工作的人”。年轻的艾伦·图灵所构想出来的机器可以将人们以往用纸笔进行的运算过程全部自动化。这台机器运作起来就像一个玩家在玩棋盘游戏——比如“大富翁”。它设有内存，而内存这个概念放到大富翁游戏棋中，就相当于棋子的位置、棋盘上的房子和玩家的资产。机器可以进入不同的运行状态，就像游戏当中会出现不同的场景。它的状态可以发生改变，好比玩家按照特定的规则推动游戏的进展。它需要来自外部的指令，遵守特定的规则，以改变运行状态，好比玩家掷出骰子以后，如果走到标有“入狱”的棋格，就得把棋子送进“监狱”。但是，与棋盘游戏不同的是，图灵机遵守的规则可以改变。事实上，规则可以由操作者输入，并储存到内存中（这就好比我们在棋盘上写下新的规则）。不仅如此，随着机器运行状态的改变，它所遵循的规则还可以进一步发生改变。（好比一个棋格上原本写着“免费停车场”，后来被改成“走进这个格子你就输了”）。在游戏规则会发生改变的情况下玩棋盘游戏，显然是一个高难度的挑战！但是试想一下，如果可以改变规则，那么整个游戏的性质都有可能发生改变，比如大富翁可以变成蛇梯棋，国际象棋可以变成西洋跳棋。
当然，图灵所指的并不是棋盘游戏。他想象的不是棋盘，而是一台能从纸带上读取信息的机器。根据即时读取的指令，机器可以将纸带左移、右移，或在纸带上读取信息、输出结果。不过，不管我们打什么样的比方来理解图灵机的运行机制，它的能力是始终如一的。图灵机是一台理论计算机。由于它可以完成任何可能的数学运算，现代计算机能做的事情都难不倒它（只不过它的运算速度要迟缓许多）。
虽然这台奇怪的新机器终究只是纸上谈兵的假想机，但是这已经足够了，因为图灵只是想从理论上解决希尔伯特提出的问题而已。或许颇具讽刺意味的是，图灵虽然提出了关于通用计算机的思想，但却并不急着证明他的机器可以解决判定问题。相反，他想证明判定问题不可能得到解决，进而说明有些问题在数学上根本不可判定。
为了做到这一点，图灵首先假想他的小计算机正在根据纸带上的信号执行一个运算，接着他提出了一个问题：有没有什么方法可以判断这台机器究竟是会陷入死循环，不停地计算下去；还是会停止计算，给出结果呢？看起来死循环的可能性很大，方法很简单，比方说在纸带A点上写上“移动到B点”，在B点上则写上“移动到A点”。
这个问题放到今天也很有现实意义，因为计算机一旦陷入死循环，或许就会“死机”，什么事情也做不了，这是我们不希望看到的。好比我们在自动取款机上输入PIN码（个人识别密码）以后，机器应该吐钱出来，而不是一动不动，什么反应也没有！
图灵认为，要想判断他的机器会不会停机，那就需要再构造一台图灵机，以对第一台机器进行检测，因为他知道，他假想的机器在理论上可以进行任何数学运算。于是他假想出第二台图灵机，如果检测到第一台图灵机永不停机，那么第二台机器就会停机，然后输出“不停机”；如果检测到第一台图灵机停了机，那么第二台机器就会一直运转下去。
现在，脑筋急转弯的地方来了。假如第二台机器反观自身，判断自己会不会停止计算，那会发生什么情况？图灵对此进行了设想，他突然发现了一个悖论：如果机器检测到自己会永不停机，那么它就会停机，然后输出“不停机”；如果机器检测到自己停了机，那么它就会一直运转下去。这在逻辑上是不可能的，由此证明，有些图灵机是不可判定的——我们永远也无法判断它们会不会停机。
尽管这样说或许令人费解、甚至不可思议，但是不可判定或不可计算的问题的确大量存在——自此之后，这样的事实一直让计算机程序员备受困扰。图灵的研究结果表明，有些数学问题是计算机无法解决的，这与计算机的运算能力、运算速度和内存容量无关。
1936年，正当年轻的图灵准备将这个振奋人心的成果公诸于世时，他偶然读到了美国数学家阿隆佐·邱奇（Alonzo Church）前不久发表的论文。那时候，全世界有好多数学家正在着手解决希尔伯特的判定问题。其中有的数学家——比如哥德尔——已经开始有了重要的研究成果。邱奇采用的方法与图灵截然不同，他需要创立新的数学概念和语言，以表述有关函数和演算过程的思想。他使用了自己创立的新语言——称为λ演算，并在哥德尔的基础上扩展了研究范围。研究结果表明，没有任何通用的算法可以判定任意两个λ表达式是否相等。也就是说，有些事情永远无法用数学方法加以判定——要想解决判定问题是不可能的。邱奇就这样率先攻克了希尔伯特挑战，他发表研究成果的时间只比图灵早了几个星期。
接下来几年里，还有其他描述算法的理论被相继提出，但它们都是等价的。邱奇的λ演算是经典的理论，它已成为计算机科学的宝贵工具，可用于对软件问题进行形式证明（7）。时至今日，它的地位依然举足轻重。不过，图灵机显然是概念方面的赢家。或许正是因为简洁易懂，图灵的计算机思想已成为理论计算机科学的基础。时至今日，连“可计算性”的定义都是根据他的思想界定出来的。“邱奇—图灵论题”（Church—Turing thesis ）得到了广泛接受，该论题认为，任何可计算的问题都可以由图灵机计算。
图灵的贡献
1936年，由于志同道合，图灵决定去美国普林斯顿大学投奔邱奇，他在那里师从邱奇，完成了博士学业。
阿隆佐·邱奇自己的经历就带有传奇色彩。他在高中时由于气枪事故，导致一只眼睛失明，后来又因为这只眼睛失明而不小心被有轨电车撞倒，因缘际会，与照看他的护士坠入爱河，步入婚姻的殿堂。邱奇平时为人彬彬有礼，衣着干净整洁，宗教信仰坚定不移，有一些出了名的怪癖，喜欢阅读和收藏科幻小说，如果发现书中有错误，他会在目录页用铅笔修改，或者致信作者予以纠正。每次讲座开始之前，他都会按部就班地把黑板擦得纤尘不染，擦拭次数非得是偶数，而且一般都要用到肥皂和水。擦完黑板后，他会耐心地等待水迹风干，要不然不会开讲。每次开讲都是长篇大论，好像在看着书稿直接念一样。如果被人打断，他会很不自然地停下来。平时说话很少不用逻辑论证。有传言说，邱奇连吃早饭的方式都很有逻辑：“先把牛奶倒进空碗里，放适量的糖，用早餐勺搅拌均匀，然后放一两勺麦片。吃完这点麦片后，再接着放一两勺，边吃边放。这样一来，糖就会在牛奶中充分溶解，分布均匀，而且麦片也不会泡得太软。”
图灵从来没有变得像邱奇那么爱干净，不过他也培养了一些高度逻辑化的习惯，而且这些习惯有时显得很古怪。博士毕业回国后，图灵喜欢戴着防毒面罩骑车，以预防花粉症。如果他发现自行车经常在他踩14圈以后掉链子，他就会每踩完13圈以后下车调整链子。
1938年，图灵回国后不久，便受到政府代码及加密学校（8）（Government Code and Cypher School）的邀请，协助军方破解德国的著名密码系统——“恩尼格玛”（9）（Enigma）。1939年英国宣战后，图灵开始在这家位于布莱切利公园的密码破译机构全职工作。他很喜欢这份工作，因为它充满挑战，而且工作环境又好。1940年，他发明了一台破译机——名为“炸弹机”（Bombe，得名于波兰的一台破译机），成功破解了德国空军传递的所有“恩尼格玛”加密情报。
到了1941年年中，德国海军的“恩尼格玛”加密情报也被全部破译。1942年至1943年3月，图灵在美国协助破译工作；尽管德军升级了密码，但事实证明，图灵的思想又一次成为了最得力的破译工具。
据估计，图灵的贡献使密码破译工作缩短了两年。这份功劳可谓功德无量，要知道，战争期间每年就有1100万人死亡。据说温斯顿·丘吉尔曾盛赞图灵，说他的工作为二战的胜利做出了最杰出的个人贡献。对于一位性格略有些古怪的极客来说，这已经是很高的赞誉了！图灵因为二战时期的杰出功劳获得了英王授予的不列颠帝国勋章（OBE），但是由于情报工作的保密性，他的功劳在接下来的三十年里一直不为人知。
二战结束后，图灵继续发挥自己的才思，开展富有开创性的研究工作。他构想了世界上最早的计算机之一——自动计算机（Automatic Computing Engine，简称ACE）。当他知道恩师马克斯·纽曼当上曼彻斯特大学（Manchester University）教授后，自己也进入了曼彻斯特大学，担任讲师的工作。任教期间，他一方面继续开展数学研究工作，另一方面扩展了兴趣范围，研究了神经科学、个体发生学（10）和量子理论。图灵是人工智能研究领域的先驱之一（我们会在后面的章节提到他的好几个思想）。1951年，他因为图灵机的研究工作而当选为伦敦皇家学会（Royal Society of London）的成员。他的大学同事并不知道，他在任教期间依然供职于英国通信总部（GCHQ，相当于国家安全局），继续参与密码破译的工作，直到冷战爆发。
1952年，图灵向警方报告了一起入室盗窃案。他承认，行窃的人正是他以前的同性伴侣的朋友。但是同性恋在当时是非法的，因此图灵被控以严重猥亵罪而遭到起诉。审讯期间，他的老朋友马克斯·纽曼为他出庭作证，但是于事无补。图灵不幸被定罪，他的选择只有两个，要么坐牢，要么接受“化学阉割”——注射女性荷尔蒙（雌激素）。他选择了注射雌激素，为此不得不遭受乳房发育等药物副作用的伤害。他不再具备参与保密工作的资格，不能再为英国政府通信总局工作。他的一举一动——无论是外出度假，还是与外国科学家开展合作——都在国安人员的密切监视之下。
图灵继续开展研究，发表了更多关于个体发生学、量子理论和相对论的论文。他四处旅行，游历了巴黎、雅典和科孚岛（Corfu，位于希腊西北部，爱奥尼亚群岛之一）。但他并不快乐。1954年，图灵被发现死在家中，身边放着咬了一口的苹果。此前他一直在做电解实验，身上可能残留了化学物质，而苹果表面检测出了氰化钾。图灵的母亲和他在通信总部的几名同事认为，这是一起事故。警方的调查结论称，他的死因是自杀。