Wednesday, July 25, 2012

计算的极限(零):逻辑与图灵机

引用松鼠会另外一篇文章里的几句话:

一个天才质疑了另一个天才,并最终证明:数学家研究的"有意义"的数学命题也可能是不可判定的。
Wir müssen wissen, wir werden wissen.
我们必须知道,我们必将知道。
这是80年前,1930年,希尔伯特在他退休时演讲的最后六个单词,也是鼓舞一代数学家的六个单词。尽管当时第三次数学危机仍然阴魂不散,但他们坚信,数学大厦的基础是坚实的。他们也坚信,任何数学真理,只要通过一代又一代人的不断努力,都能用逻辑的推理将其整合到数学的大厦中。
这是何等的气魄!这是何等的梦想!
但就在演讲前夕,他的同胞哥德尔,作出了一个断言,彻底打碎了这个梦。

 
 

Sent to you by Tony via Google Reader:

 
 

via 科学松鼠会 by 方弦 on 7/16/12

本文作者:方弦

【提出问题和解决问题的人】

2012,图灵诞辰100周年,献给这位伟大的开拓者。

计算无处不在。

走进一个机房,在服务器排成的一道道墙之间,听着风扇的鼓噪,似乎能嗅出0和1在CPU和内存之间不间断的流动。从算筹算盘,到今天的计算机,我们用作计算的工具终于开始量到质的飞跃。计算机能做的事情越来越多,甚至超越了它们的制造者。上个世纪末,深蓝凭借前所未有的搜索和判断棋局的能力,成为第一台战胜人类国际象棋世界冠军的计算机,但它的胜利仍然仰仗于人类大师赋予的丰富国际象棋知识;而仅仅十余年后,Watson却已经能凭借自己的算法,先"理解"问题,然后有的放矢地在海量的数据库中寻找关联的答案。长此以往,工具将必在更多的方面超越它的制造者。而这一切,都来源于越来越精巧的计算。

计算似乎无所不能,宛如新的上帝。但即使是这位"上帝",也逃不脱逻辑设定的界限。

第一位发现这一点的,便是图灵。

一切从逻辑开始

1900年的巴黎,在世纪交替之际,希尔伯特提出了他著名的23个问题。其中第二个问题——算术系统的相容性——正是他那雄心勃勃的"希尔伯特计划"的最后一步。这位数学界的巨人,打算让整个数学体系矗立在一个坚实的地基上,一劳永逸地解决所有关于对数学可靠性的种种疑问。一切都为了回答三个问题:

数学是完备的吗?也就是说,面对那些正确的数学陈述,我们是否总能找出一个证明?数学真理是否总能被证明?

数学是一致的吗?也就是说,数学是否前后一致,不会得出某个数学陈述又对又不对的结论?数学是否没有内部矛盾?

数学是可判定的吗?也就是说,能够找到一种方法,仅仅通过机械化的计算,就能判定某个数学陈述是对是错?数学证明能否机械化?

希尔伯特明确提出这三个问题时,已是28年后的1928年。在这28年间,数学界在算术系统的相容性上没有多少进展。但希尔伯特没有等太久,仅仅三年后,哥德尔就得到了前两个问题的答案,尽管这个答案不是希尔伯特所希望看到的。

哥德尔的答案分两部分。

第一,任何包含了算术的数学系统都不可能同时拥有完备性和一致性,也就是说,如果一个数学系统包含了算术的话,要么它是自相矛盾的,要么存在一些命题,它们是真的,但我们却无法证明。这说明,希尔伯特的前两个问题不可能同时为真。在这里,"算术"有着精确的含义,就是皮亚诺公理,一组描述了自然数的公理。

第二,任何包含了算术的数学系统,如果它是一致的,那么我们不能在它的内部证明它本身的一致性。这说明,我们没有希望解决第二个问题。

这就是著名的哥德尔不完备性定理,与其说它回答了希尔伯特的前两个问题,不如说它阐述了为什么我们根本不可能解决这两个问题。

哥德尔的证明非常精巧。他先将所有的数学陈述和证明符号化,然后给每个符号串赋予一个数字,这个过程被称为哥德尔配数法。借助数学归纳法,我们可以建立针对所有自然数的陈述,而这样的陈述本身对应着一个数字,这个数字也符合陈述本身的要求。换言之,这个陈述陈述了它本身的性质。哥德尔正是通过这样魔法般的自指,完成了他的证明。这个证明之所以重要,是因为它第一次提供了一套完整的数学工具和方法,用于证明有关数学证明的不可能性。这本身就是数学的一次重大胜利,说明数学的力量强大得可以用纯粹逻辑的方法,证明它本身的力量是有界限的。在数学的领地上,有些东西我们不知道,也不可能知道。

希尔伯特的前两个问题已经解决,只剩下最后一个问题。然而,如果一个数学系统不完备的话,它显然不可能是可判定的,因为机械化的计算本身也可以看成一种证明,而在一个不完备的系统中,真理不总能被证明。所以,最后一个问题只对完备的数学系统有意义。

所幸,完备的数学系统是存在的。同样是哥德尔,他证明了所谓"一阶谓词演算"的逻辑系统是完备的,这被称为哥德尔完备性定理。一阶谓词演算是一个比较弱的逻辑系统,在其中我们甚至不能有效唯一地描述算术。比如说,自然数系统符合皮亚诺公理的一阶版本,但它并不是唯一的,还有无数种所谓"非标准模型"同样符合这套一阶系统。在一阶谓词演算中,对于一套公理系统,如果一个命题在所有的模型中都正确,那么必定可以形式地证明这个命题,这就是一阶谓词演算的完备性。在一阶谓词演算中,真理总能被证明。

在这个弱得多的逻辑系统中,我们有了完备性,真的命题必定可以被证明。那么,它是不是可判定的?我们能不能找到一种机械计算的方法,判定其中数学陈述的对错?数学称述的真假,是否可判定的?这个问题,就是希尔伯特的可判定性问题。

注:希望更深入了解哥德尔不完备性定理的读者,可以重温旧文《希尔伯特之梦,以及梦的破灭》

复杂的简单机器

在纽曼教授的数理逻辑课上,图灵第一次听到希尔伯特的可判定性问题以及哥德尔不完备性定理。那是1935年的春天,他刚刚完成在剑桥国王学院的四年本科学习,以优异的成绩被选为学院研究员,正准备在数学界大显身手,数理逻辑自然而然吸引了他的兴趣。图灵清楚地意识到,解决可判定性问题的关键,在于对"机械计算"的严格定义。考究希尔伯特的原意,这个词大概意味着"依照一定的有限的步骤,无需计算者的灵感就能完成的计算",这在没有电子计算机的当时,算是相当有想象力又不失准确的定义。

但图灵的想法更为单纯。什么是"机械计算"?机械计算就是一台机器可以完成的计算,这就是图灵的回答。

用机器计算的想法并不新鲜。17世纪的莱布尼兹就曾设想过用机械计算来代替哲学家的思考,而19世纪的Charles Babbage和Ada Lovelace就设计出了功能强大的"分析机",只可惜Babbage欠缺管理才能,这台超越了时代的机器始终没有完全造好。但图灵需要的机器,跟先驱设想的机器稍有不同。它必须足够简单,简单得显然能造出实物,也可以用一目了然的逻辑公式描述它的行为;它又必须足够复杂,有潜力完成任何机械能完成的计算。图灵要找的,是一种能产生极端复杂行为的简单机器。

这并非易事,但图灵做到了,据说这是他某次长跑过后,在某块草坪上发呆的成果。他设计了一类机器,然后定义"机械计算"为"这类机器可以完成的计算"。他设计的这类机器,正是日后以他名字命名的图灵机。

图灵机的示例。绿点指示处为当前状态,每条规则的4项分别是:当前位置读入的字符、当前位置写入的字符、纸带的移动方向、将要转移到的状态。

图灵机的结构非常简单,它由两部分组成:一个读写头,还有一条两边无限延长的纸带,纸带被划分为小格,每格中只能有0和1两种符号。读写头的限制则稍微宽松一些,虽然每次只能对着纸带上的一个格子,但它本身可以处于不同的状态,虽然状态的数目是有限的。在所有状态中,有一个特殊的"停机"状态,读写头一旦处于停机状态,就会停止运作;但如果读写头一直没有到达停机状态的话,它就会永远运转下去。

整台图灵机的秘密在于读写头的状态转移表,它指示着读写头的状态和当前读写头正对格子的符号如何变化。它只有一种非常简单的规则,就是"如果在状态A的读写头对着符号x,那么对当前格子写入符号y,将纸带左移一格/右移一格/保持不动,然后转移到状态B"。状态转移表就是由一系列这样的简单规则组成的。可以说,状态转移表就相当于图灵机的源代码。

实际上,我们平时笔算乘法的思维过程,跟一台图灵机的运转非常相似:在每个时刻,我们只将注意力集中在一个地方,根据已经读到的信息移动笔尖,在纸上写下符号;而指示我们写什么怎么写的,则是早已背好的九九乘法表,以及简单的加法。如果将一个笔算乘法的人看成一台图灵机,纸带就是用于记录的纸张,读写头就是这个人和他手上的笔,读写头的状态就是大脑的精神状态,而状态转移表则是笔算乘法的规则,包括九九表、列式的方法等等。这种模式似乎也适用于更复杂的机械计算任务。如此看来,图灵机虽然看起来简单,但它足以作为机械计算的定义。

既然图灵机如此简单,能不能将它"升级",赋予更多的硬件和自由度,使它变得更强大呢?比如说,让它拥有多条纸带和对应的读写头,而纸带上也不再限定两种符号,而是三种四种甚至更多种符号?的确,放宽限制之后,在某种程度上,对于相同的任务我们能设计出更快的图灵机,但从本质上来说,"升级"后的图灵机能完成的任务,原来的图灵机也能完成,虽然也许会慢些。也就是说,这种"升级"在可计算性上并没有意义,放宽限制后的机器能计算的,原来的机器也能完成。既然计算能力没有质的变化,无论采取什么样的结构,用多少种符号,都无所谓。

图灵机的一大优点,就是它的简单。只要给出状态转移表,任何一个人都可以模拟一台图灵机的计算。对工程师而言,在现实中用机械建造一台图灵机也并非什么难事。对于程序员来说,写一个模拟图灵机的简单程序更是不在话下。但如此简单的机器,它又能做什么呢?它真的能充当"机械计算"的定义吗?

(未完待续)


 
 

Things you can do from here:

 
 

Monday, July 9, 2012

我的社交网络自动同步流程图

之前一直纠结怎么在各种社交网站之间自动同步状态和博文,用了各种诡异的方法。
前一段时间才发现,对于状态同步而言,用微博通(wbto.cn)似乎可以解决大部分问题。
这幅图是我自动同步的流程,细线是状态的同步路线,粗线是博客文章的同步路线;红线是手动的同步路线,黑线是自动的同步路线。
以后如果我闲着没事,可能再会更新这张图。
好吧,这篇文章主要是测试一下flickr的照片共享功能。。。。
p.s.: 果然flickr的外链有问题,也可能是我的设置有问题,回归到Google Drive了。。。
p.s.2: Google Drive也有问题,于是又回来Picasaweb了。。。。



Sunday, July 8, 2012

面对面的办公室——纪念艾伦•图灵百年诞辰zz

梦回那个风起云涌,激情燃烧的年代。比起来现在我做的那些research简直弱爆了。。。
想看全文请移步至:
http://www.douban.com/note/221426825/
原文作者拒绝转载。

 
 

Sent to you by Tony via Google Reader:

 
 

via 科学松鼠会 by 科学松鼠会 on 7/6/12

本文作者:科学松鼠会

【图片出处:http://www.cs.swan.ac.uk/~csarnold/

作者:玑衡

本文节选自作者为纪念艾伦•图灵诞辰一百周年所写,全文发表在豆瓣(http://www.douban.com/note/221426825/)。那段壮丽、斑驳、甚至诡秘的历史,在作者的笔下放射出人性的光芒,而这,却仿若只是图灵身上光芒的万千之一。

这里先截取文章的一部分以飨读者。

一、左边的办公室

冯•诺伊曼教授每年换一部新凯迪拉克。早上十点,他把爱车停在帕尔玛物理实验室门口,神采奕奕地走进隔壁数学系的办公室。那时候普林斯顿高等研究院才刚成立,和数学系挤在一幢叫作Fine Hall的楼—— "还不错的楼"。冯•诺伊曼教授总是穿一身笔挺的西装,以免别人把他错当成学生。他太年轻,三十出头,却已经到达了学术顶峰,和五十多岁的物理学家爱因斯坦、数学家维布伦(Oswald Veblen)、数学家亚历山大(James Alexander)一起成了高等研究院最初任命的四位教授。

【John von Neumann, 1903-1957】

十八岁那年,他犹太裔的父母试图把长子拉出对数学的执迷学些更实际的东西,于是他们达成了妥协,冯•诺伊曼同时在三所大学注册:在苏黎士联邦理工学院(ETH)学习化学工程,每晚完成柏林大学数学专业的作业,在每个学期末回布达佩斯大学参加他从没上过课的数学考试。二十二岁那年他不但从苏黎士联邦理工拿到化学工程学位,还通过了大卫•希尔伯特坐镇的数学博士答辩。整场答辩希尔伯特只问了一个问题:"我从来没见过这么漂亮的晚礼服,你的裁缝是谁?"于是,大家都知道了,希尔伯特钦点的年轻人,不但写了完美的博士论文,还是个翩翩佳公子。

博士毕业后的三年,高产的三年!他在柏林大学和汉堡大学的三年一共发表了二十五篇论文!包括一本八十年后仍然重印的量子力学教科书,可是……对于这个高速前行的天才这些光荣也已经是陈年往事。二十七岁上,纳粹刚刚抬头而美国也恰好走出了大萧条,维布伦代表普林斯顿去欧洲招兵买马,工资开价是冯•诺伊曼在德国挣的八倍还多。踏进美利坚第一天,他打趣地对同行的匈牙利老乡维格纳(Eugene Wigner, 1963年诺贝尔物理学奖)说:"我们该让自己更像美国人。"当即,维格纳改名叫"尤金"(Eugene),冯•诺伊曼改名叫"约翰"(John),和稍微熟一点的人就勾肩搭背地说"你们叫我强尼(Johnny)吧。"

强尼,强尼。强尼•冯•诺伊曼就不着痕迹地混进了满大街都是强尼的美利坚大熔炉,还有谁知道他刚出生时那个卑微的匈牙利名"亚诺斯"(Janos) ?还有谁知道他在德国那几年日耳曼化的"约汉纳"(Johann)? 不过他改了名字,却死活不肯把姓氏里的"冯"去掉。二十几年前他有钱的犹太老爸向行将就木的老皇帝弗朗茨•约瑟夫买了这个贵族称号,于是带着暴发户气息的诺依曼家族就转眼变成了代代相传的贵族冯•诺伊曼,多亏奥匈帝国国库空虚等钱用,否则十足的犹太血统怎么能捐上这个高贵的名头?一到周末冯•诺伊曼肯定请教授们上他宽敞奢侈的大宅喝酒跳舞,宾客盈门杯觥交错, "冯•诺伊曼请客谁不去!"讲出这话,就好象请客做东的是奥匈帝国的某个最尊贵的日耳曼裔公爵。

二、右边的办公室

冯•诺伊曼教授对面的办公室坐着博士生艾伦•图灵。开朗外向的冯•诺伊曼教授和孤僻紧张的图灵没什么闲话好聊,只知道这个总穿一身乱糟糟运动衫的年轻人前几天差点把自己的那部二手福特车倒车进了卡耐基湖。冯•诺伊曼教授横穿大西洋必买头等舱,常年西装革履,每年换一部崭新的凯迪拉克,略略发福,讨厌运动,有一次妻子想让他学滑雪他恼羞成怒甚至以离婚威胁。与他恰恰相反,博士生图灵则在几个月前坐着末等甲板舱从英国漂到美国。他常年一件套头衫,开一部状况堪忧的二手福特,身材瘦削,热爱运动,是跑赢过奥运会选手的马拉松健将。一到周末,他和同学打垒球比赛,分成两个队,"大英帝国队"对决"叛变殖民地队"。

【Alan Turing, 1912-1954】

刚来普林斯顿那会儿他不是没试过去交朋友,拥抱新生活,可是上个月当一名卡车司机理所当然地把自己油腻腻的手搭在他肩上直呼其名和他侃大山时,堂堂剑桥大学国王学院的毕业生着实为这种粗鲁的风气吓了一跳。别误会了,他不像冯•诺伊曼教授那样公子派头,他爸爸不过是大英帝国驻印度的一个小公务员,可是英伦岛国的教养让他觉得一个陌生人把脏手搭在你他肩上实在有点亲昵过分。他也讨厌陌生人叫他"艾伦",还是"图灵先生"更妥当些。除了难以适应美国的新环境,图灵先生还有更糟的问题,在那个年代的体面社会里止于手势和眼神的问题:喏,你知道的,他有点那个……就是那个……那个啊……你晓得我在讲什么啊。

数学天才艾伦•图灵先生是个无可救药的同性恋。

这个无可救药的问题是这样开始的:当图灵还在谢伯恩男校 (Sherborne School )读高中,他认识了比自己高一级的克里斯托弗•马尔孔 (Christopher Morcom)。瘦弱的、过于瘦弱的马尔孔,每个学年都因病长期缺课,可他聪明的头脑竟然使他在偶尔上学的几天能补上所有功课,门门考试成绩第一。是这样毫不费力的聪慧吸引了图灵,而当他更接近马尔孔,惊喜地发现他和自己一样,对科学有着自发而浓厚的兴趣。在马尔孔偶尔上学的日子里,他们坐在相邻的座位听课,又一起去图书馆写作业,以便能不断讨论科学问题:马尔孔说如何在家里搭化学实验室研究碘,图灵说如何手算圆周率到小数点后36位,马尔孔说你知不知道薛定谔的量子力学有趣极了,图灵说你知不知道爱因斯坦的相对论也有趣极了。他们谈梦想,应该做数学家还是物理学家,如何为科学做出真正的贡献……晚钟响了,他们回各自的宿舍睡觉,又在凌晨爬起来站到阳台上用天文望远镜看星星,并写信把观测结果告诉对方:"我从没见过更好的木星。今夜我看到了五个环,甚至能看清中间那个环上的斑。""我今夜看到了仙女座,但一会儿就消失了。"那个冬天,毕业班的马尔孔已顺利拿到了剑桥三一学院的奖学金。图灵还有一年毕业,马尔孔鼓励他来年报考剑桥,"因为那里的科学最好,而且我能经常看见你。"这句嘉勉说出口不到一个月,一个晴朗的凌晨,图灵起床看见月亮刚巧经过对楼马尔孔的窗户落下。"今晚的月亮格外美。"他写在记事本上预备第二天告诉马尔孔,他还不知道永远不会有那一天了。那个凌晨,克里斯托弗•马尔孔暴病夭折。

落葬日,时年十七岁的图灵怀着巨大的悲痛写信给马尔孔的母亲:

1930年2月15日

亲爱的马尔孔太太,

我因为克里斯而很难过。一年来我们一起学习,我从来没交过像他那么聪明、迷人、又谦卑的朋友。我和他分享了研究的乐趣还有对天文的热爱(这是他引发的),我想他也是这么觉得的。现在,尽管有一部分乐趣因为他的死而消逝了,即使这一切不再因为他而那么有趣,我也要投入尽可能多的精力到研究上,就象他仍然活着。他会希望我这么做的。我深知你此刻的悲痛。

你忠诚的,

艾伦•图灵

又及:如果你能给我一张克里斯的小照片我将十分感激。我愿以此来缅怀他的榜样和成就,督促我更仔细更优秀。我会思念他的面容,他走在我身边时微笑的模样。幸好我保存着他所有的信。

马尔孔死后一年,图灵的未来决定了,他要去剑桥国王学院学数学,就像给马尔孔太太的信里所承诺的,"以此缅怀他的榜样和成就。"这一年中,无数次对马尔孔的哀思恐怕也让他渐渐明白了比友谊更深的感情。是爱情吗?图灵无法回答,也不屑回答。落葬日那封痛切的信,还有这一年来(以及他的余生)为了纪念马尔孔而突飞猛进的学业都说明了这份感情比爱情更高:他在竭尽所能挽留死者。又有谁会为那么美好的感情而惊慌呢?于是图灵坦然接受了,并在余生从未试图遮掩自己的性取向。

【图灵和克里斯托夫,第一张图左侧的机械装置出自密码破译机"Bombe",这将在文章后面提到。图片出处:http://www.polarimagazine.com/

三、希尔伯特的落日

每个清晨和黄昏,图灵习惯一个人沿着河边长跑思考问题。去年夏天,当他还在剑桥国王学院读本科,某次长跑到精疲力竭地躺倒在草地上,斜阳西照,运动让他神思凝聚,他脑中经历了一场风暴,忽然意识到了回答希尔伯特判定问题(Entscheidungsproblem)的办法。他兴奋地一跃而起跑回寝室写下自己的思绪。他的身后,照耀世界数学界三十余年之久的希尔伯特的太阳,终于落山了。

大卫•希尔伯特,那个时代最受尊敬的数学家,凭一己之力使数学走上了更严谨系统的现代之路。1900年,38岁的希尔伯特如一位新任的武林盟主,振臂一呼,四方响应。他在国际数学大会上提出了著名的"二十三个问题",立即成为了数学界集体奋斗的目标,其中的第八个问题黎曼猜想/哥德巴赫猜想更是成了数学的桂冠。二十八年后,暮年的希尔伯特又提出了三个数理逻辑上的大问题,简单说来这三个问题分别是:1)数学是完备的吗?2)数学是相容的吗?3)数学是可判定的吗?其中的第三问题,即被称作希尔伯特的判定问题。如果说 1900年的二十三个难题洋溢着壮年人的踌躇满志,那么1928年的三个问题已经是一个老人对秩序和条理的向往。希尔伯特十分希望,这三个问题的答案都是肯定的,因为这将使数学建立在完美严谨的逻辑的基石上,作为亘古不变的真理存在。

可惜,这个井井有条的逻辑美梦只做了三年,年轻的奥地利人哥德尔就发表了震惊数学界的哥德尔不完备定理:数学不可能既是完备的又是相容的。这个定理以十分有趣的形式否定了希尔伯特1928年的第一和第二个问题。到1935年夏天,躺在草地上休息的图灵经历了一场头脑风暴,他想到了否定希尔伯特第三个问题的办法:用机器。他想象着一种虚构的"图灵机",可以从一条无限长的纸带子上的读取命令进行操作,从而模拟人类所可能进行的任何计算过程。图灵证明,我们不能用一个算法来判定一台给定的图灵机是否会停机,所以停机问题是一个无法判定的数学问题,即希尔伯特的第三个命题答案为否。

巧合的是,第二年春天,正当图灵把关于判定问题的论文初稿交给导师纽曼(Max Newman)过目时,大洋彼岸,普林斯顿大学的阿隆佐•邱奇(Alonzo Church)教授——逻辑界数一数二的学者——抢先一步发表了新论文,利用自创的λ演算(lambda calculus)否定了希尔伯特判定问题。看到邱奇如此巧合的论文,导师纽曼顺水推舟写信推荐图灵去做博士生。1936年夏,邱奇的新博士生图灵来到了普林斯顿。

【图灵在普林斯顿大学的档案 Firestone Library, Princeton University, June 2012。由本文作者在实地拍摄】

11月,图灵关于判定问题的论文,即多年后将声名大噪的 On Computable Numbers, with an Application to the Entscheidungsproblem 终于发表,学界反应极其冷淡。12月图灵在普林斯顿数学俱乐部做了关于这篇论文的演讲,听众不足十人。这篇解决了希尔伯特第三个问题的论文为何遭到如此冷遇?有几个原因:其一,哥德尔不完备定理如此有趣奥妙,已经吸引走了学界关于希尔伯特三问题的大部分兴趣;其二,邱奇当年春天的论文已经率先解决了希尔伯特判定问题,虽然图灵的解法天差地别,也比邱奇的解法简洁得多;其三,用"机器"解决数理逻辑问题,实则是此篇论文最闪光的部分,可是过于新颖,不容易被主流学界接受;其四,恐怕也是最重要的原因:和著名教授邱奇比起来,图灵才初出茅庐。他在家书中愤愤说:"只有名人才会吸引听众。(One should have a reputation if one hopes to be listened to.)"

 

不,不完全如此。至少还有一个人会认真阅读无名小卒的论文。对门办公室的冯•诺伊曼教授——图灵默默仰慕又羞于开口的偶像——不但认真读过这篇论文,还读过所有期刊上的所有论文。他是一本雄心勃勃的百科全书,任何人的任何知识都逃不出他的法眼。图灵的论文一发表,敏锐的冯•诺伊曼已经嗅到了图灵机广阔的远景,他对朋友说,你该去找我对门的图灵,他那篇论文正好可以做这样那样的事。他慷慨地给朋友建议,自己却没亲自找图灵聊聊。他的注意力在有趣的图灵机上停留了一下,又跳到另一个截然不同却同样有趣的问题上:量子力学、流体力学、博弈论……世上千千万的问题都吸引着冯•诺伊曼,他脑中有千千万要实行的计划——图灵机不过是其中一个。

可是,博士生图灵仍然因为这篇论文而给冯•诺伊曼教授留下了印象,两年后图灵从普林斯顿博士毕业,是冯•诺伊曼教授唯一提出了挽留:年薪一千五百美元聘图灵做自己的助手。对于一个年轻的数学家,能师从传奇般的冯•诺伊曼教授是梦寐以求的机遇, 一千五百美元的薪水也比图灵在英国能找到的教职待遇好得多。图灵拿着冯•诺伊曼的聘书在普林斯顿校园里晃荡,理性使他不得不好好考虑这个千载难逢的肥缺,可是啊——英国人图灵吸吸鼻子,鼻子里呼到的空气有点太粗鄙,清清耳朵,耳朵里听到的英语有点太懒散。他走过哥特式的普林斯顿校礼拜堂,那只是更加宏伟古老的剑桥国王学院礼拜堂蹩脚的复制品。礼拜堂的尖顶插入新泽西州的蓝天白云,英国人图灵却没法欣赏这儿的晴空万里,他的目光越到了大西洋彼岸,那里,纳粹的阴云密布欧洲。

1938年夏,博士毕业的图灵忧心忡忡回到英国剑桥,在数学系做一学期才给十英镑的临时教员,教一门听者寥寥的"数学基础"。他将慢慢攀爬学术的梯子,成为教员、讲师、副教授、教授,如果不出意外的话。九个月后,意外降临:纳粹的阴云终于骤降成狂风暴雨,德国入侵波兰,第二次世界大战开始。

四、Station X. Site Y.

二战的爆发给白金汉郡的布莱切利镇带来了点可喜的新鲜,一万多人连夜从大城市挤火车逃难到这个平庸乏味的小镇,可是不久大部分又挤火车回去了:宁愿被炸弹炸死,也不要在这小地方无聊死。艾伦•图灵却逆着人潮,搬到了这无聊小镇最无聊郊区的一家最最无聊的小旅馆里,每天骑车三英里去镇中心的布莱切利园(Bletchley Park)上一个谁都不知道在瞎搞什么的班,下班回来还自愿给冷冷清清的旅馆酒吧打杂。旅馆老板娘看着这个闲得发慌的小伙直摇头:健健康康的大男人,怎么不去打仗呢?

可是,图灵正在打仗。他的敌人:哑谜。看似死水一潭的布莱切利园,此时已有了军事代号:Station X,保密等级:绝密。这里是英国政府密码学校的驻地,海陆空和军情六处的情报组织各占一隅。几百名工作人员日夜兼程破解德国人的无线电报,为了最大程度保密,大部分职员根本不知道工作的真正目的,除了几个核心解密成员:象棋冠军、填字游戏高手、数学家。二十七岁的图灵很快在这个核心团队里有了绰号:教授(Prof.)。

此时的欧洲上空,无数来自德军的电波正以莫尔斯码的形式穿梭来回。这些莫尔斯码发出前由一种称作"哑谜机"(the Enigma Machine)的加密器加密,在接受方又由同样的"哑谜机"解密。直到二战结束,德军从未怀疑过哑谜机的坚不可摧,所有军种所有级别电报,一律用哑谜机加密,加密电报中放心大胆地沟通了所有军事信息:潜艇位置、军队人数、攻击路线、伤亡报告……

【哑谜机】

德军的信心源于哑谜机复杂的加密方法。虽然每个军种对商用的哑谜机都略有改进,不过所有哑谜机基本构造相同:键盘、接线板、多个转子、指示灯。当密码操作员在键盘上按下一个字母(比如字母A),电流会通过一个可自行改接的接线板,启动一个或者多个转子转动,同时点亮某个字母指示灯(比如字母L),于是字母A被加密成字母L。哑谜机精巧的设计使得,在下一次按下字母A时,它将被加密成另一个不同的字母(比如字母P)。更巧妙的是,当且仅当发送端和接收端的哑谜机拥有同样的初始设定(同样的接线板、同样的转子排列、同样的转子初始位置),密码L才可以使用接收端的哑谜机还原成A。而对于不知道初始设定的敌方,他们面对的可能情况多达10^114种!

雪上加霜的是,德军每个军种所用的哑谜机略有不同,相对于三个转子的陆军哑谜机,海军五转子的哑谜机要复杂得多。在布莱切利园只有两个人相信这层层加密状如天书的密码可以被破解:一个是布莱切利园的老大,因为"海军电报必须被破解",否则被德军潜艇战封锁的英国将坐以待毙;另一个是"教授"图灵,因为"如果海军电报能破解,那实在太好玩了"。

"教授"发现,在加密文件中找规律的本质是重复搜索,而搜索是一种机器可以代替人脑的工作。当时,布莱切利园从曾经研究过哑谜机的波兰数学家那里继承了一种叫"炸弹"(Bombe)的原始解密仪器,每一个"炸弹"模仿一个哑谜机的转子,许多"炸弹"相链接来模拟一种哑谜机的初始设定生成可能的电报。简而言之,这是一种穷举搜寻答案的算法,需要遍历所有可能排列,费时费力。图灵洞察到,只要运用几个简单的事实——比如,一个字母的密码不可能是其本身、原始文本中一些字母(比如s)的出现频率一定高于另一些字母(比如x),一些固定词语(比如"元首")将高频出现——就能大大改进波兰人的笨法子,来快速寻找最有可能的转子设定。用现在的算法语言来说,他将穷举法改良成了贪心算法。贪心算法改进后的"炸弹"对抗五转子的海军哑谜机大获成功。每次一方发出电报后,接受方过几分钟将发一封短电报表示"收讫"。许多回,电波中还未监测到"收讫"电报,图灵的"炸弹"机已经将密码还原成了原文, 可见"炸弹"的解密速度甚至比预知原始设定的接受方都快!布莱切利园自豪地说,德国人真该问"教授"他们的电报到底讲了什么。

可是,随着战争深入,转子更多的哑谜机不断投入运用,最后竟出现了十二转子的密码机。面对十二转子,即使图灵的"炸弹"都需要十几天时间。战场瞬息万变,布莱切利园亟需更快速的机器。很显然,提高速度的关键在于把机械的"炸弹"机改成更快速的电路装置。1943年,在图灵的鼓励下,布莱切利园工程师Tommy Flowers设计了一台叫作Colossus的巨型机器,在战时充裕的经费支持下很快获准建造。

这就是世界上第一台计算机,电子化、数字化、程序化。它由光学在长条纸带上读取电报原文,经过一千五百个真空管的电路计算,将解密结果输出到电传打字机上。1944年6月1日, 经过完善的Colossus二号机抵达布莱切利园。离诺曼底登陆只有五天。

诺曼底登陆,在欧洲开辟第二战场的唯一方法,毋宁是一场豪赌。盟军三百万主力兵力要从海上和空中登陆易守难攻的诺曼底,很可能伤亡惨重。为了保护兵力,盟军的情报网精心编造了一则假情报透露给敌方,希望德军以为在诺曼底将有一次只是"小规模"的军事转移。而德军能不能上当则唯有通过由Colossus解密的德军电报检验。幸亏快速的电子计算机,解密很顺利,德军的电报显示只有一小支部队被派往诺曼底。更幸运的是,电报还详细说明了军事安排、物资转移、军种调遣,德军手中的牌一览无余。

6月6日凌晨三点,Colossus破解了一条德军自诺曼底刚发出的绝望的电报。天啊,天上怎么来了那么多伞兵。

随着这些伞兵安然降落,二战的转折点到来了。

大西洋的另一边,1943年秋。

威斯康辛大学麦迪逊分校数学教授乌拉姆(Stan Ulam)的办公室里闯进了一个女学生。学期只过了一半,她却要求提前完成期末考试,以便"为战争服务"。她坐在办公室的地板上,答完了教授在信封背面临时写下的几道题,然后消失到谁都不知道哪儿去了。

这几天,乌拉姆身边有许多朋友消失了。在食堂认识的同事、物理教授、自己带的研究生,他们打了个 "为战争服务"的假条,就神秘莫测地走了。乌拉姆心里痒痒,写信给自己朋友中人脉最广的冯•诺伊曼,询问有否能为战争服务的工作,他回信了,说自己忙得很,不如在芝加哥火车站见面——他在那里正好有两个小时的转车时间。乌拉姆在站台见到了风风火火的冯•诺伊曼,以及——他身后的两位保镖,这才意识到他朋友正在忙活的事对大战意义重大。冯•诺伊曼神秘地表示:有一件很重要的项目也许能让乌拉姆帮忙,不过他还不能说是什么事,在哪里,有谁。

几周后,乌拉姆收到了一封政府委派信,要求他去新墨西哥州一个小镇。他从来没听说过这荒僻之地,就去图书馆借新墨西哥州地图册。于是他惊喜地发现,在地图册的借书卡上,整齐地排列着之前消失的所有熟人的名字。他们都消失到了这个闻所未闻之地。

火车在一个荒凉的车站停下,黄沙遍野,峭壁陡崖,像时间尽头一样死寂。这里就是Site Y,刚刚起步的研究项目叫Project Y,保密等级:绝密。战争结束后,前者将称为洛斯阿拉莫斯国家实验室(Los Alamos National Laboratory),后者便是鼎鼎大名的曼哈顿计划。在这片萧索瑰丽的沙漠中,聚集了一群活力旺盛的年轻人,平均年龄25岁,第一年,80个新生命诞生。他们的领袖奥本海默38岁,他们的信使冯•诺伊曼39岁。他们的任务:制造摧毁一切活力和生命的超级武器,原子弹。

【洛斯阿拉莫斯国家实验室边界的标志】

四年前,爱因斯坦和西拉德(Leo Szilard)上书美国总统罗斯福:物理学的推进已经使得通过核裂变获得巨大能量指日可待,只要德国人愿意,他们有知识和能力发明这种武器,美国必须赶在纳粹德国之前掌握核技术。随着美国正式参战,核技术的研究越来越紧迫。一个名字被提出来:罗伯特•奥本海默,聪明果敢,当机立断。另一个名字被提出来:约翰•冯•诺伊曼,因为他已经坐镇另外十几个军事项目上,正好能耳听八路,眼观四方。

冯•诺伊曼教授是军方最喜爱的合作人。作为犹太人他对纳粹嫉恶如仇,为了替关在集中营的朋友报仇他渴望和手段强硬的人合作,醉心各种新式武器。作为数学家,他认为只有当数学有应用价值时,数学才能最快速度发展。少时父亲逼迫之下学习的化学工程意外派上了用场,他很容易明白物理学家和化学家的讨论,再用数学的语言解释给数学家听。他最擅长把一项看似庞大无解的任务庖丁解牛,分拆成小零件委派他人,让底下每个人觉得自己拿到的那部分恰好是最擅长的本职。他是天生的领袖和传令官,坐镇导弹研究实验室、美国数学学会战争委员会、国家防御研究委员会……不像大多数被强制定居在洛斯阿拉莫斯的科研者,他进出自由。日理万机的冯•诺伊曼教授哟,他在普林斯顿、波士顿、费城、华盛顿、芝加哥、洛斯阿拉莫斯实验室、阿伯丁兵器试验中心……全美的战时科研进展他一清二楚,人家刚跟他讲了两句,他就能接上来,"某某在芝加哥也做这事。""哈佛的某某已经搞出来了。"

曼哈顿计划最大的困难不是制造出核裂变反应,而是控制原子弹的威力。爆炸的冲击波将反复震荡叠加,最终的力量难以预测。曼哈顿计划的高度机密性和核试验的昂贵成本使得大规模试验不可能,而人力又难以计算如此多的非线性方程。如何提高计算能力成了当务之急。

事实上,计算能力这个瓶颈也困扰着其他军方科研项目。于是,1943年,当听说宾夕法尼亚大学的一群工程师为了计算导弹轨道(另一种典型的非线性方程)而开始建造一台名为ENIAC的巨型机器时,冯•诺伊曼立即敏锐地想到:也可以用这机器去计算原子弹冲击波的能量。在他的牵头下,ENIAC建完后第一项测试任务居然不是导弹轨道而成了核弹方程,整个测试将原本几个月的 人力计算缩短到了几天。完成测试他脸色苍白地回到普林斯顿家里倒头睡了十小时,醒来后不吃不喝,久久向妻子吐出一句话:"我们造了一头怪兽。"

怪兽,他指的不是核弹,而是计算机。

看到了ENIAC的广阔前景后,冯•诺伊曼毛遂自荐要做ENIAC的数学顾问,让发明者Presper Eckert和John Mauchly受宠若惊。他们亲自领冯•诺伊曼参观机器,一间两百平米的大房间里,两个工程师指给他看:这里是一万八千根真空管、这里是电源、这里是读卡器、这里是维修站……可是,人家的设计冯•诺伊曼却看得比设计者还清楚,他一回去就写了个105页的报告:"一台计算机的基础组成是:存储器、控制器、运算器、输入输出设备。"至今,世界上的大部分电脑仍在沿用这著名的"冯•诺伊曼结构"。

1945年5月,德国投降,证据显示德国当时的科研进展还未能制造出原子弹。7月,洛斯阿拉莫斯第一颗原子弹试射成功。8月,在新上任的杜鲁门总统的授意下,两颗本为抵御德国人的原子弹投向日本广岛和长崎。9月,日本投降。第二次世界大战结束。

【1945年7月16日凌晨,第一颗原子弹Trinity在新墨西哥州试射成功。】

图灵战后的故事,近期放出……


 
 

Things you can do from here: