1937年,在Church的帮助下,图灵的那篇论文(起名为《Computable Numbers》)终于发表了。Church还是很器重图灵的,他把图灵的机器叫做“图灵机”。不幸的是,论文发表之后,学术界对此几乎没有任何反响,只有两人向图灵索取这篇论文。图灵当然不爽了,于是后来就到处推销自己的图灵机,想让大家承认那是伟大的发明。有了一个锤子,看什么都是钉子。后来每到一个地方,每做一个项目(见下一节),他都想把问题往自己那篇论文和图灵机上靠,东拉西扯的想证明它的价值,甚至称别人发明的东西全都是受到了图灵机的启发…… 经过人们很长的时间的以讹传讹之后,他终于成功了。
图灵当年的作法,其实跟当今计算机学术界的普遍现象差不多。我想发表自己的想法A,结果别人已经发表了B,解决了A要解决的问题,而且还比A简单和清晰。怎么办呢?首先,我声明自己从没看过B的论文,这样就可以被称为“独立的发现”。然后,我证明A和B在“本质”上是等价的。最后,我东拉西扯,挖掘一下B的局限性,A相对于B在某些边沿领域的优势…… 这样反复折腾,寻找A的优势,总有一天会成功发表的。一旦发表成功,就会有人给我唱高调,没用的东西也要说成是有用的。他们会在A的基础上发展他们自己的东西,最后把我推崇为大师。那发表更早,更简单优美的B,也就无人问津了。胜利!
现在不得不说一下《图灵传》对此的歪曲。Church的论文发表,比图灵的论文投稿还早一年,而且Church使用了比图灵机更简单优雅的计算模型。Church的成果本来天经地义应该受到更多的尊重,到头来作者却说:“...and Turing was robbed of the full reward for his originality”(见第3节“The Turing machine”)。让人感觉貌似是Church用不正当的手段“抢走”了图灵的“原创性”一样。你本来没有什么原创性,还丑陋复杂,所以何谈抢走呢?我怎么觉得恰恰相反,其实是图灵抢走了Church的原创性?现在提起Hilbert可判定性问题,可计算性理论,人们都想起图灵,有谁还想得起Church,有谁知道他是第一个解决了这问题的人,有谁知道他用了更优美的办法?
Lambda演算与计算理论由于图灵到处推销自己的理论,把不好的东西说成是好的,把别人发明的机器硬往自己的理论上面靠,说他们受到了图灵机的“启发”,以至于很多人被蛊惑,以为它比起lambda演算确实有优势。再加上很多人为了自己的利益而以讹传讹,充当传教士,这就是为什么图灵机现在被人们普遍接受作为计算模型。然而这并不能改变它丑陋和混淆的本质。图灵机的设计,其实是专门为了证明Hilbert的可判定性问题不可解决,它并不是一个用途广泛的计算模型。图灵机之所以被人接受,很大部分原因在于人的无知和愚蠢。很多人(包括很多所谓“理论计算机科学家”)根本没好好理解过lambda演算,他们望文生义,以为图灵机是“物理的”,实际可用的“机器”,而lambda演算只是一个理论模型。
事实恰恰相反:lambda演算其实非常的实用,它的本质跟电子线路没什么两样。几乎所有现实可用的程序语言,其中的语义全都可以用lambda演算来解释。而图灵机却没有很多现实的意义,用起来非常蹩脚,所以只能在计算理论中作为模型。另外一个更加鲜为人知的事实是:lambda演算其实在计算理论方面也可以完全取代图灵机,它不但可以表达所有图灵机能表达的理论,而且能够更加简洁和精确地表达它们。
很多理论计算机科学家喜欢用图灵机,仿佛是因为用它作为模型,能让自己的理论显得高深莫测,晦涩难懂。普通的计算理论课本,往往用图灵机作为它的计算模型,使用苦逼的办法推导各种可计算性(computability)和复杂性(complexity)理论。特别是像Michael Sipser那本经典的计算理论教材,晦涩难懂,混淆不堪,有时候让我都怀疑作者自己有没有搞懂那些东西。
后来我发现,其实图灵机所能表达的理论,全都可以用更加简单的lambda演算(或者任何一种现在流行的程序语言)来表示。图灵机的每一个状态,不过对应了lambda演算(或者某种程序语言)里面的一个“AST节点”,然而用lambda演算来表示那些计算理论,却可以比图灵机清晰和容易很多。在Indiana大学做计算理论课程助教的时候,我把这种思维方式悄悄地讲述给了上课的学生们,他们普遍表示我的这种思维方式更易理解,而且更加贴近实际的编程。
举一个很简单的例子。我可以用一行lambda演算表达式,来显示Hilbert的“可判定性问题”是无解的:
Halting(λm.not(Halting(m,m)), λm.not(Halting(m,m)))
完整的证明不到一页纸,请看我的另外一篇文章(英文)。这也就是图灵在他的论文里,折腾了十多页纸证明的东西。
我曾经以为自己是唯一知道这个秘密的人,直到有一天我把这个秘密告诉了我的博士导师,Amr Sabry。他对我说:“哈哈!其实我早就知道这个,你可以参考一下Neil Jones写的一本书,叫做《Computability and Complexity: From a Programming Perspective》。这本书现在已经可以免费下载。
此书作者用一种很简单的程序语言,阐述了一般人用图灵机来描述的那些理论(可计算性理论,复杂性理论)。他发现用程序语言来描述计算理论,不但简单直接,清晰明了,而且在某些方面可以更加精确地描述图灵机无法描述的定理。得到这本书,让我觉得如获至宝,原来世界上有跟我看法如此相似,对事物洞察力如此之高的人!
在一次会议上,我有幸地遇到了Neil Jones,跟他切磋思想。当提到这本书的模型与图灵理论的关系,老教授谦虚地说:“图灵的模型还是有它的价值的……” 然而到最后,他其实也没能说清楚这价值何在。我心里很清楚,他只是为了避免引起宗教冲突,或者避免显得狂妄自大,而委婉其词。眼前的这位教授,虽然从来没有得过图灵奖,很少有人听说过他的名字,然而他对于计算本质的理解,却比图灵本人还要高出很多。
总的说来,图灵机也许不是一文不值,然而由于lambda演算可以更加清晰地解释图灵机能表示的所有理论,图灵机的价值相对来说几乎为零。Church在1937年给图灵论文写的Review指出,图灵机的优势,在于它可以让不懂很多数学,不理解lambda演算之类理论的人也可以看得懂。我怎么觉得图灵机对于不懂很多数学的人,理解起来其实更加痛苦呢?而且就算它真的对“外行”或者“笨人”的理解有好处,这价值貌似也不大吧?:P
图灵当年的作法,其实跟当今计算机学术界的普遍现象差不多。我想发表自己的想法A,结果别人已经发表了B,解决了A要解决的问题,而且还比A简单和清晰。怎么办呢?首先,我声明自己从没看过B的论文,这样就可以被称为“独立的发现”。然后,我证明A和B在“本质”上是等价的。最后,我东拉西扯,挖掘一下B的局限性,A相对于B在某些边沿领域的优势…… 这样反复折腾,寻找A的优势,总有一天会成功发表的。一旦发表成功,就会有人给我唱高调,没用的东西也要说成是有用的。他们会在A的基础上发展他们自己的东西,最后把我推崇为大师。那发表更早,更简单优美的B,也就无人问津了。胜利!
现在不得不说一下《图灵传》对此的歪曲。Church的论文发表,比图灵的论文投稿还早一年,而且Church使用了比图灵机更简单优雅的计算模型。Church的成果本来天经地义应该受到更多的尊重,到头来作者却说:“...and Turing was robbed of the full reward for his originality”(见第3节“The Turing machine”)。让人感觉貌似是Church用不正当的手段“抢走”了图灵的“原创性”一样。你本来没有什么原创性,还丑陋复杂,所以何谈抢走呢?我怎么觉得恰恰相反,其实是图灵抢走了Church的原创性?现在提起Hilbert可判定性问题,可计算性理论,人们都想起图灵,有谁还想得起Church,有谁知道他是第一个解决了这问题的人,有谁知道他用了更优美的办法?
Lambda演算与计算理论由于图灵到处推销自己的理论,把不好的东西说成是好的,把别人发明的机器硬往自己的理论上面靠,说他们受到了图灵机的“启发”,以至于很多人被蛊惑,以为它比起lambda演算确实有优势。再加上很多人为了自己的利益而以讹传讹,充当传教士,这就是为什么图灵机现在被人们普遍接受作为计算模型。然而这并不能改变它丑陋和混淆的本质。图灵机的设计,其实是专门为了证明Hilbert的可判定性问题不可解决,它并不是一个用途广泛的计算模型。图灵机之所以被人接受,很大部分原因在于人的无知和愚蠢。很多人(包括很多所谓“理论计算机科学家”)根本没好好理解过lambda演算,他们望文生义,以为图灵机是“物理的”,实际可用的“机器”,而lambda演算只是一个理论模型。
事实恰恰相反:lambda演算其实非常的实用,它的本质跟电子线路没什么两样。几乎所有现实可用的程序语言,其中的语义全都可以用lambda演算来解释。而图灵机却没有很多现实的意义,用起来非常蹩脚,所以只能在计算理论中作为模型。另外一个更加鲜为人知的事实是:lambda演算其实在计算理论方面也可以完全取代图灵机,它不但可以表达所有图灵机能表达的理论,而且能够更加简洁和精确地表达它们。
很多理论计算机科学家喜欢用图灵机,仿佛是因为用它作为模型,能让自己的理论显得高深莫测,晦涩难懂。普通的计算理论课本,往往用图灵机作为它的计算模型,使用苦逼的办法推导各种可计算性(computability)和复杂性(complexity)理论。特别是像Michael Sipser那本经典的计算理论教材,晦涩难懂,混淆不堪,有时候让我都怀疑作者自己有没有搞懂那些东西。
后来我发现,其实图灵机所能表达的理论,全都可以用更加简单的lambda演算(或者任何一种现在流行的程序语言)来表示。图灵机的每一个状态,不过对应了lambda演算(或者某种程序语言)里面的一个“AST节点”,然而用lambda演算来表示那些计算理论,却可以比图灵机清晰和容易很多。在Indiana大学做计算理论课程助教的时候,我把这种思维方式悄悄地讲述给了上课的学生们,他们普遍表示我的这种思维方式更易理解,而且更加贴近实际的编程。
举一个很简单的例子。我可以用一行lambda演算表达式,来显示Hilbert的“可判定性问题”是无解的:
Halting(λm.not(Halting(m,m)), λm.not(Halting(m,m)))
完整的证明不到一页纸,请看我的另外一篇文章(英文)。这也就是图灵在他的论文里,折腾了十多页纸证明的东西。
我曾经以为自己是唯一知道这个秘密的人,直到有一天我把这个秘密告诉了我的博士导师,Amr Sabry。他对我说:“哈哈!其实我早就知道这个,你可以参考一下Neil Jones写的一本书,叫做《Computability and Complexity: From a Programming Perspective》。这本书现在已经可以免费下载。
此书作者用一种很简单的程序语言,阐述了一般人用图灵机来描述的那些理论(可计算性理论,复杂性理论)。他发现用程序语言来描述计算理论,不但简单直接,清晰明了,而且在某些方面可以更加精确地描述图灵机无法描述的定理。得到这本书,让我觉得如获至宝,原来世界上有跟我看法如此相似,对事物洞察力如此之高的人!
在一次会议上,我有幸地遇到了Neil Jones,跟他切磋思想。当提到这本书的模型与图灵理论的关系,老教授谦虚地说:“图灵的模型还是有它的价值的……” 然而到最后,他其实也没能说清楚这价值何在。我心里很清楚,他只是为了避免引起宗教冲突,或者避免显得狂妄自大,而委婉其词。眼前的这位教授,虽然从来没有得过图灵奖,很少有人听说过他的名字,然而他对于计算本质的理解,却比图灵本人还要高出很多。
总的说来,图灵机也许不是一文不值,然而由于lambda演算可以更加清晰地解释图灵机能表示的所有理论,图灵机的价值相对来说几乎为零。Church在1937年给图灵论文写的Review指出,图灵机的优势,在于它可以让不懂很多数学,不理解lambda演算之类理论的人也可以看得懂。我怎么觉得图灵机对于不懂很多数学的人,理解起来其实更加痛苦呢?而且就算它真的对“外行”或者“笨人”的理解有好处,这价值貌似也不大吧?:P