剑桥1935
现在,艾伦·图灵是一个家喻户晓的名字,但我们很难想象在20世纪80年代,这个名字在数学和计算机领域以外压根不为人知。虽然相关专业的学生可以在教材上偶遇图灵的名字,但对他非凡的成就知之不详,更不了解他那悲惨的命运。部分原因是图灵在第二次世界大战期间为英国政府效力,承担了一项非常重要的工作,而这项杰出工作的成果一直秘而不宣,直到20世纪70年代才公开[1] 。但是,更重要的原因是歧视,因为图灵是同性恋,在当时的英国,同性恋是一种犯罪。1952年,他以“严重猥亵罪”被起诉和定罪,被迫服用某种旨在降低性欲的粗制滥造的药物来进行所谓的“化学阉割”。两年后,他亲手结束了自己的生命,年仅41岁[2] 。
尽管如今的我们对图灵的故事所知甚少,但多少略知一二。其中最著名的桥段自然是二战期间他在布莱切利庄园破译密码的传奇,因2014年好莱坞电影《模仿游戏》而天下皆知(虽然电影和现实的差距大得惊人)。他为盟军的最终胜利立下了汗马功劳。但是,人工智能研究人员和计算机科学家崇拜图灵,是出于完全不同的理由:他是真正意义上的计算机发明者,不久,又成为人工智能领域的主要奠基人。
图灵在诸多领域都有非凡成就,最非凡的是在偶然的机会下,他发明了计算机。20世纪30年代中期,图灵还是剑桥大学数学系的一名学生,他给自己定下一个超前的挑战,那就是解决彼时最重要的终极数学问题之一:判定问题 。这个令人印象深刻——坦率地说,是可怕——的问题,由数学家大卫·希尔伯特(David Hilbert)于1928年提出。判定问题是指,是否所有的数学描述都是“可判定的”,即是否存在一种方法,可以确认某个给定的数学描述是真是假。当然,希尔伯特关心的领域并非“有没有上帝”或者“生命的意义是什么”之类,而是数学领域中的判定问题。判定问题是一种有着明确“是”或“否”的答案的数学问题。以下是判定问题的示例:
· 2 + 2是否等于4?
· 4×4是否等于16?
· 7919是否是一个质数?
很凑巧,这几个问题的答案都是“是”。前两个问题的答案是显而易见的,但是,除非你是个痴迷于质数的人,否则要回答第三个问题得稍微费点儿劲了。所以,我们来看看最后一个问题。
你应该记得,质数的定义是一个只能被自己和1整除的整数。现在回到这个问题,我相信从原则上讲,你能够寻找到一个验证它的方法。有一个很容易想到的笨办法,当然,对7919这么大的数字来说有些烦琐:依次用每一个整数去除它,看看它能不能被某个数除尽。重复这个过程以后,你会发现,除了1和7919本身,没有其他可以除尽它的数,这就意味着7919确实是一个质数[3] 。
重点在于,上述问题可以用一个精准的方式来寻找答案。
这种方式不需要任何灵活的应用——只是一些需要死记硬背的方法。要寻找答案,我们只需要严格按照方法所示的步骤执行就可以。
既然有这样的方法保证能够验证这个问题的是与否(只要有足够的时间),我们就可以说,“某个数是否是一个质数”是可判定问题 。在此我强调一下,这就意味着,每当我们遇见“数n是否是一个质数”这样的问题时,只要给予足够的时间,就能找到答案:遵循相关步骤执行,最终就能得到明确的答案。
现在,判定问题提出:是否所有的数学判定问题都是可判定的?或者说,是否存在某种数学问题,无论你投入多少时间,都无法寻找到相应的可供严格遵循来解决问题的方法?
这是一个基础法则类问题,本质是数学问题是否都可以简化为寻找对应算法就可以解决的问题。回答这个基础问题是图灵在1935年给自己立下的艰巨挑战,而他以令人难以置信的惊人速度解答出来了。
一想到深奥的数学问题,我们很容易就会认为解决它们的方法是冗长而复杂的,涉及大篇幅的方程式和证明过程。有时候,事实的确是这样,例如英国数学家安德鲁·威尔斯(Andrew Wiles)在20世纪90年代论证著名的费马大定理,数学界花费了好几年时间才消化了他那几百页的手稿,并确信他的论证是正确的。按照这样的标准,图灵解决判定问题的方案简直是颠覆性的。
与大家想象中的不同,图灵的证明短小精悍,而且很容易读懂(在确立了基本框架以后,真正的证明实际上只有几行)。重点在于,图灵意识到,他需要一个精准定义解决问题方法的方案,为此,他发明了一种可以解决数学问题的机器,如今,为了纪念他,我们称之为图灵机 。图灵机是一种对方法的具体描述,比如上文提到的检查质数的步骤。图灵机的作用是严格遵循既定的步骤执行运算。在此,我要强调的是,尽管图灵将它称为“机器”,但在那时它只是个抽象的数学概念。通过发明一台机器来解决一个艰深的数学问题,这种想法相当颠覆传统,当年的数学家们肯定都被搞迷糊了。
图灵机就如强悍的神兽,任何你能想出来的数学方法都可以被编码成图灵机。因此,如果所有的判定问题都是可以解决的,就意味着任何判定问题都可以通过设计一个专用的图灵机来解决。也就是说,为了解答希尔伯特的问题,你所要做的是,证明存在某种判定问题是任何图灵机都无法解决的。这正是图灵证明这一命题的方法。
接下来,图灵耍了点小把戏,让他的机器摇身一变,成为能够解决通用问题的机器。他设计了一种图灵机,可以按照人们给它的任意方法进行运算,现在我们把它称为通用图灵机[4] 。一台计算机最核心也最基础的部分,就是一台真正的通用图灵机。计算机所运行的程序,本质上就是运算的步骤,类似前文我们提到的确认质数的步骤。
尽管这不是我们故事的重点,但至少得提出来图灵是怎么用它的新发明解决判定问题的。除了惊叹于他精巧独到的心思,我们还应该意识到,它跟人工智能最终是否可能存在有着密切关系。
图灵的构想是存在这样一台图灵机,可以用来判定任意图灵机的运行结果。他考虑了以下问题:给定一台图灵机和相关输入集,它最终是会停止,还是永无止境地运行下去?这就是一个判定问题了,属于我们前文讨论过的范畴,尽管它相对复杂一些。现在,假设存在一个机器能够判定这个判定问题,图灵指出,这个假设会引起悖论[3] 。因此,没有办法检测出图灵机是否停止。那么,“图灵机是否停止”是一个不可判定问题 。所以图灵得出结论:存在某些判定问题不能简单地按照确定的步骤来解决。他解决了希尔伯特的难题:数学并不能被简化为遵循方法解决问题[5] 。
这一结果是20世纪数学界最伟大的成就之一,单凭它就足以让图灵在数学界名垂青史。但更伟大的是它的副产物——通用问题解决机器,即图灵机。图灵发明图灵机的时候,它只是个抽象的概念,他并没有想着将它实体化。不过没过多久,不少人,包括图灵自己,开始着手把这个想法转化成现实。在二战时的慕尼黑,康拉德·楚泽(Konrad Zuse)为德国航天部设计了一台名为Z3的计算机,虽然它算不上一台完整的计算机,但引入了不少关键部分。在大西洋彼岸的美国宾夕法尼亚州,由约翰·穆克里(John Mouchly)和普雷斯伯·埃克特(J. Presper Eckert)领导的小组开发了一台名为ENIAC的机器来计算火炮射击表。杰出的匈牙利裔数学家约翰·冯·诺依曼(John von Neuman)对它进行了相关调整,使ENIAC具备现代计算机的基本架构(为了纪念这位数学家,传统计算机的架构被称为“冯·诺依曼架构”)。在战后的英国,弗雷德·威廉姆斯(Fred Williams)和汤姆·基尔伯恩(Tom Kilburn)建造了昵称为“曼彻斯特宝贝”的小规模实验机,直接促成了世界上第一台商用计算机“费兰蒂一号”的出现(图灵本人于1948年加入曼彻斯特大学的工作团队,并编写了最早运行的程序)。
到了20世纪50年代,现代计算机的所有关键部件都被发明出来了。图灵机已经从数学概念转化为实实在在的机器——只要你有足够的金钱买下它,以及足够的场地摆放它(要装下“费兰蒂一号”,至少需要两个16英尺[4] 长、8英尺高、4英尺宽的储藏室。机器的功率为27千瓦——它消耗的电能可以供应至少三个现代家庭用电)。当然,随着时代的发展,计算机变得越来越小巧,越来越便宜。
本书评论