图灵最重要的贡献,就是改进波兰人的BOMBA,设计了一个更好的机器叫BOMBE。BOMBE比起BOMBA,其实并没有质的飞跃,只不过BOMBE同时模拟的Enigma机器更多,转的更快。另外它加入了一些“优化”措施,尽早排除不可行的路径,所以速度快很多。图灵最初的设计,要求必须能够事先猜出很长的文本,所以基本不能用。后来Gordon Welchman发明了一种电路,叫做diagonal board,才使Bombe能够投入实用。关于Gordon Welchman的故事,你可以参考这个BBC纪录片。
在Bombe能够投入使用之前,有一个叫John Herivel的人,发现了一种特殊的技巧,叫做Herivel tip,这种技术在Bombe投入使用之前几个月就已经投入实用,破解掉很多德军的消息,立下汗马功劳。如果Herivel tip没有被发明,盟军可能在1940年5月就已经战败,BOMBE也就根本没机会派上用场。
同时在Bletchley Park,还诞生了一台大型可编程电子计算机Colossus,它是由一个叫Tommy Flowers的工程师设计的。Colossus不是用来破解Enigma密码的,而是用于破解Lorenz SZ-40。那是一种比Enigma还要先进的密码机器,用于发送希特勒的最高指令。
德国人后来又改进了他们的通信方式,使用了一种具有四个齿轮的Enigma机器。这大大的增加了破解的难度,普通的Bombe机器也破不了它了。后来是Harold Keen设计了一个叫做Mammoth的机器,后来加上美国海军的帮助,制造了更快的Bombe,才得以破解。
所以你看到了,所有这些人的工作加起来,才改善了二战的局面。波兰人的BOMBA,已经包含了最重要的思想。图灵的工作其实更多是量的改进,而不是质的飞跃。现在很多人喜欢跟风,片面的夸大图灵在其中的作用,这是不对的。如果你对Enigma机器的技术细节感兴趣,可以参考这两个视频:[视频1][视频2]。
理论计算机科学
图灵被称为“计算机之父”,计算机科学界的最高荣誉,被叫做“图灵奖”(Turing Award)。然而如果你深入的理解了计算理论和程序语言理论就会发现,图灵对于理论计算机科学,其实并没产生长远而有益的影响。在某种程度上说,他其实帮了一个倒忙。图灵的理论复杂不堪,给人们造成很大的误导,阻碍了计算机科学的发展。而且他对于发表论文,对待研究的态度让我怀疑,我觉得图灵本人其实就是当今计算机学术界的一些不正之风的鼻祖。
图灵机和lambda演算绝大部分计算机专业的人提到图灵,就会想起图灵机(Turing Machine)。稍微有点研究的人,可能知道图灵机与lambda演算在计算能力上的等价性。然而在“计算能力”上等价,并不等于说它们具有同样的价值,随便用哪个都无所谓。科学研究有一条通用的原则:如果多个理论可以解释同样的现象,取最简单的一个。虽然lambda演算和图灵机能表达同样的理论,却比图灵机简单,优雅,实用很多。
计算理论(Theory of Computation)这个领域,其实是被图灵机给复杂化了。图灵机的设计是丑陋,复杂,缺乏原则的。它的读写头,纸带,状态,操作,把本来很简单的语义搞得异常复杂。图灵机的读写两种操作同时发生,这恰好是编程上最忌讳的一种错误,类似于C语言的i++。图灵机是如此的复杂和混淆,以至于你很难看出它到底要干什么,也很难用它清晰地表达自己的意思。这就是为什么每个人上“计算理论”课程,都会因为图灵机而头痛。如果你挖掘一点历史,也许会发现图灵机的原型,其实是图灵母亲使用的打字机。用一台打字机来建模所有的计算,这当然是可行的,然而却复杂不堪。
相比之下,lambda演算更加简单,优雅,实用。它是一个非常有原则的设计。Lambda演算不但能清晰地显示出你想要表达的意思,而且有直接的“物理实现”。你可以自然的把一个lambda演算表达式,看成是一个电子线路模块。对于现实的编程语言设计,系统设计,lambda演算有着巨大的指导和启发意义。以至于很多理解lambda演算的人都搞不明白,图灵机除了让一些理论显得高深莫测,还有什么存在的意义。
历史的倒退图灵机比起lambda演算来说,其实是一个历史的倒退。1928年,Alonzo Church发明了lambda演算(当时他25岁)。Lambda演算被设计为一个通用的计算模型,并不是为了解决某个特定的问题而诞生的。1929年,Church成为普林斯顿大学教授。1932年,Church在Annals of Mathematics发表了一篇论文,纠正逻辑领域里几个常见的问题,他的论述中用了lambda演算。1935年,Church发表论文,使用lambda演算证明基本数论中存在不可解决的问题。1936年4月,Church发表了一篇两页纸的“note”,指出自己1935年那篇论文可以推论得出,著名的Hilbert“可判定性问题”是不可解决的。
1936年5月,当时还在剑桥读硕士的图灵,也写了一篇论文,使用自己设计的一种“计算机器”(后来被叫做图灵机)来证明同一个问题。图灵的论文投稿,比Church最早的结论发表,晚了整整一年。编辑从来没见过图灵机这样的东西,而且它纷繁复杂,远没有lambda演算来得优雅。就像所有人对图灵机的第一印象一样,编辑很难相信这打字机一样的操作方式,能够容纳“所有的计算”。他无法确定图灵的论述是否正确,只好找人帮忙。Church恐怕是当时世界上唯一能够验证图灵的论文正确性的人。所以一番好心之下,编辑写了封信给Church,说:“这个叫图灵的年轻人很聪明,他写了一篇论文,使用一种机器来证明跟你一样的结果。他会把论文寄给你。如果你发现他的结果是正确的而且有用,希望你帮助他拿到奖学金,进入Princeton跟你学习。”
图灵就是这样成为了Church的学生,然而图灵心高气傲,恐怕从来没把Church当成过老师,反倒总觉得Church抢先一步,破坏了自己名垂青史的机会。跟Church的其它学生不一样,图灵没能理解lambda演算的精髓,却认为自己的机器才是最伟大的发明。进入Princeton之后,图灵不虚心请教,只是一心想发表自己的论文,想让大家对自己的“机器”产生兴趣,结果遭到很大的挫折。当然了,一个名不见经传的人,做了个怪模怪样的机器,说它可以囊括宇宙里所有的计算,你不被当成民科才怪呢!
在Bombe能够投入使用之前,有一个叫John Herivel的人,发现了一种特殊的技巧,叫做Herivel tip,这种技术在Bombe投入使用之前几个月就已经投入实用,破解掉很多德军的消息,立下汗马功劳。如果Herivel tip没有被发明,盟军可能在1940年5月就已经战败,BOMBE也就根本没机会派上用场。
同时在Bletchley Park,还诞生了一台大型可编程电子计算机Colossus,它是由一个叫Tommy Flowers的工程师设计的。Colossus不是用来破解Enigma密码的,而是用于破解Lorenz SZ-40。那是一种比Enigma还要先进的密码机器,用于发送希特勒的最高指令。
德国人后来又改进了他们的通信方式,使用了一种具有四个齿轮的Enigma机器。这大大的增加了破解的难度,普通的Bombe机器也破不了它了。后来是Harold Keen设计了一个叫做Mammoth的机器,后来加上美国海军的帮助,制造了更快的Bombe,才得以破解。
所以你看到了,所有这些人的工作加起来,才改善了二战的局面。波兰人的BOMBA,已经包含了最重要的思想。图灵的工作其实更多是量的改进,而不是质的飞跃。现在很多人喜欢跟风,片面的夸大图灵在其中的作用,这是不对的。如果你对Enigma机器的技术细节感兴趣,可以参考这两个视频:[视频1][视频2]。
理论计算机科学
图灵被称为“计算机之父”,计算机科学界的最高荣誉,被叫做“图灵奖”(Turing Award)。然而如果你深入的理解了计算理论和程序语言理论就会发现,图灵对于理论计算机科学,其实并没产生长远而有益的影响。在某种程度上说,他其实帮了一个倒忙。图灵的理论复杂不堪,给人们造成很大的误导,阻碍了计算机科学的发展。而且他对于发表论文,对待研究的态度让我怀疑,我觉得图灵本人其实就是当今计算机学术界的一些不正之风的鼻祖。
图灵机和lambda演算绝大部分计算机专业的人提到图灵,就会想起图灵机(Turing Machine)。稍微有点研究的人,可能知道图灵机与lambda演算在计算能力上的等价性。然而在“计算能力”上等价,并不等于说它们具有同样的价值,随便用哪个都无所谓。科学研究有一条通用的原则:如果多个理论可以解释同样的现象,取最简单的一个。虽然lambda演算和图灵机能表达同样的理论,却比图灵机简单,优雅,实用很多。
计算理论(Theory of Computation)这个领域,其实是被图灵机给复杂化了。图灵机的设计是丑陋,复杂,缺乏原则的。它的读写头,纸带,状态,操作,把本来很简单的语义搞得异常复杂。图灵机的读写两种操作同时发生,这恰好是编程上最忌讳的一种错误,类似于C语言的i++。图灵机是如此的复杂和混淆,以至于你很难看出它到底要干什么,也很难用它清晰地表达自己的意思。这就是为什么每个人上“计算理论”课程,都会因为图灵机而头痛。如果你挖掘一点历史,也许会发现图灵机的原型,其实是图灵母亲使用的打字机。用一台打字机来建模所有的计算,这当然是可行的,然而却复杂不堪。
相比之下,lambda演算更加简单,优雅,实用。它是一个非常有原则的设计。Lambda演算不但能清晰地显示出你想要表达的意思,而且有直接的“物理实现”。你可以自然的把一个lambda演算表达式,看成是一个电子线路模块。对于现实的编程语言设计,系统设计,lambda演算有着巨大的指导和启发意义。以至于很多理解lambda演算的人都搞不明白,图灵机除了让一些理论显得高深莫测,还有什么存在的意义。
历史的倒退图灵机比起lambda演算来说,其实是一个历史的倒退。1928年,Alonzo Church发明了lambda演算(当时他25岁)。Lambda演算被设计为一个通用的计算模型,并不是为了解决某个特定的问题而诞生的。1929年,Church成为普林斯顿大学教授。1932年,Church在Annals of Mathematics发表了一篇论文,纠正逻辑领域里几个常见的问题,他的论述中用了lambda演算。1935年,Church发表论文,使用lambda演算证明基本数论中存在不可解决的问题。1936年4月,Church发表了一篇两页纸的“note”,指出自己1935年那篇论文可以推论得出,著名的Hilbert“可判定性问题”是不可解决的。
1936年5月,当时还在剑桥读硕士的图灵,也写了一篇论文,使用自己设计的一种“计算机器”(后来被叫做图灵机)来证明同一个问题。图灵的论文投稿,比Church最早的结论发表,晚了整整一年。编辑从来没见过图灵机这样的东西,而且它纷繁复杂,远没有lambda演算来得优雅。就像所有人对图灵机的第一印象一样,编辑很难相信这打字机一样的操作方式,能够容纳“所有的计算”。他无法确定图灵的论述是否正确,只好找人帮忙。Church恐怕是当时世界上唯一能够验证图灵的论文正确性的人。所以一番好心之下,编辑写了封信给Church,说:“这个叫图灵的年轻人很聪明,他写了一篇论文,使用一种机器来证明跟你一样的结果。他会把论文寄给你。如果你发现他的结果是正确的而且有用,希望你帮助他拿到奖学金,进入Princeton跟你学习。”
图灵就是这样成为了Church的学生,然而图灵心高气傲,恐怕从来没把Church当成过老师,反倒总觉得Church抢先一步,破坏了自己名垂青史的机会。跟Church的其它学生不一样,图灵没能理解lambda演算的精髓,却认为自己的机器才是最伟大的发明。进入Princeton之后,图灵不虚心请教,只是一心想发表自己的论文,想让大家对自己的“机器”产生兴趣,结果遭到很大的挫折。当然了,一个名不见经传的人,做了个怪模怪样的机器,说它可以囊括宇宙里所有的计算,你不被当成民科才怪呢!