计算机科学是伪科学吗?
// 计算机科学是伪科学吗?
这个问题曾经一度让我焦虑过好多天,作为一个理想成为科学家的人,这个问题的答案对我来说意义重大。在我越来越多地了解计算机科学(computer science)后,内心却对CS属于Science产生了越来越多的怀疑。在一篇和这个问题相关的有些消极和偏激 但其观点我非常认同的文章(https://unqualified-reservations.blogspot.com/2007/08/whats-wrong-with-cs-research.html)里,作者认为所谓的CS researchers 基本上可以划分为这样三类人:有创造力的程序员,数学家和学术官僚。先抛开这个问题不谈,这本书讲的就是这三类人中我觉得最有趣的那类人的故事:计算机学科中的数学家。
//我不知道我本科都学了什么
我记得我本科的时候除了要学习编程之外,还要修离散数学、数理逻辑等基础课程。大概是由于自己天性愚钝懒散,加上教书和写书(or 抄书?)的人水平有限,教学枯燥乏味,那时候我并不明白学这些无聊的课有什么意义。直到我在国外读研期间修了一些计算理论方面的课之后,我才逐渐理解了在计算机系统和编程技术这些花里胡哨的东西背后的数学/逻辑理论基础。这本书从一个更宏观更开阔的视角和计算历史发展的角度把逻辑和计算领域里最基本的理论——它们各自扮演的角色以及它们之间的关系——认真梳理了一遍。读完这本书我感觉像是找到了一条线,把我学过的那些零七八碎的东西串成一条珍珠项链。
// 关于书的内容
这本书大体按照时间顺序(穿越3个世纪)讲了7位逻辑学家/数学家(莱布尼茨,布尔,弗雷格,康托,希尔伯特,哥德尔,图灵)的故事,一半是关于他们生平的传记性内容,另一半则是深入浅出地介绍和探讨了他们对这个领域的重要贡献。从莱布尼茨开始设想一种通用的可以用来推理演算的符号系统,到布尔构建出可用的逻辑代数,然后弗雷格引入量词结构把一阶逻辑扩展到二阶乃至高阶;20世纪最伟大的数学家之一希尔伯特认为数学一定是完备的,然而康托在研究无限的过程中提出的对角线证明方法和哥德尔的不完备定理看起来有着惊人的相似,宣告了希尔伯特的理想的破灭;几乎是在同一时期 图灵在自己完全独立的工作过程中构想出一个更巧妙的方法证明出了同样的结论,并且附带发展出一个计算模型——通用图灵机,这个计算模型是计算科学领域公认的基础计算模型,我们现在讨论算法的时间或空间复杂度的度量都是基于这个模型,而我们讨论一个形式语言(或一个编程语言)是否具有通用的计算能力(Turing-complete)时,即是要证明这个语言和图灵机模型的表达能力是等价的。
// 番外
除了主线故事以外,书中也提到图灵的博士导师丘奇也在和图灵同一年的时间用另一种完全不同的方法发展出了一种可以描述计算的本质的系统。这个被他称为lambda calculus(中文翻译多见是 λ演算子)的方法,不同于图灵机的简单直观、将计算完全机械化的思想,是一种对高阶逻辑的函数式的抽象表示,简洁优雅,表达能力更强,但同时牺牲了直观性和易理解性。因此在电子计算机的发明过程中,工程师们对图灵机的模型普遍更容易接受。受到图灵机模型的深刻影响和启发,冯诺依曼结构这种经典的现代计算机模型得以形成。但是其实图灵机和 λ演算子被证明具有完全相等的计算能力,也就是说它们完全可以解决相同的问题。在我看来,这两个模型的思维方式的区别就如同使用命令式编程语言(比如C语言)和纯函数式编程语言(如Haskell)编程的区别。FORTRAN语言之父在获1977年的图灵奖时发表了一篇文章《Can Programming Be Liberated From the von Neumann Style?》,副标题 A functional style and its algebra of programs,然后我看到函数式编程最近二三十年来在学术领域迅速崛起(抑或只是我在受我的导师的“忽悠”。。。),从高层次抽象的形式表达和证明到低层次的操作系统/并发研究,以及其在并行计算领域具有先天优势的突出亮点。然后现在似乎也是开始进入了平台期。
// 有激情 有基情 还要不怕差钱
看完这本书一个让我唏嘘不已的事实是,这7位科学家似乎没有一个(大概除了希尔伯特)后半辈子过上了理想的生活并且寿终正寝的,他们的工作要么不被当时的社会环境认可,要么得不到足够的经费支持。莱布尼茨靠着给公爵修家族谱过活,科研只能作为副业;布尔一生辛苦赚钱养活一大家子,不到50岁就得肺炎死了;康托长期遭到舆论攻击精神崩溃;哥德尔更惨,后半辈子都是活在精神疾病的折磨中,最后因为被害妄想症绝食死的;至于图灵的故事,想必在卷福拍了电影模拟游戏(The Imitation Game)之后也应该是家喻户晓了。
// 关于翻译 //或: 好书我都推荐读原版
翻译大体还是流畅的,可以看得出译者也是下了一番功夫的良心译者。但是大概是因为译者不是CS专业人员,一些专业知识方面的翻译还是有漏洞的,还有一些重要的原理解释的翻译也有些别扭(不确定译者自己是否理解正确。。。),比如reduce这个术语很多地方被翻译成“还原”,但在CS专业书里更多的是翻译成“归约”(这是一种在算法和计算理论里很常见的证明方法:通过把一个问题A“归约”到另一个问题B,从而证明这两个问题具有同样的复杂度——B的解也可以用作A的解,或者说找到A的解不会比找到B的解更困难),所以后半部分我直接找来英文原版读的。 但是如果没有译者的贡献,我可能还不会知道这本书。所以感谢译者的工作,让我遇到一本好书。以原作者(算是图灵的师弟)的水平和他对这些理论的理解高度,这本书完全值得二刷或者更多刷。
// 计算机科学是伪科学
如果我们把“科学”只限定为“自然科学”这个领域的话,CS目前确实是伪科学。但这不代表这个领域就没有有趣的值得深入研究的东西了。一个做IT交互设计的朋友曾经跟我说过,她对于科技对人类生活的影响有着深刻的体会,因为她的工作是让新技术变得对人类更友好更易用,她认为自然科学的研究工作固然是伟大的,但是前沿科技的研究也同样意义非凡,尤其是计算机技术可以更快速地转化成生产力,带动别的学科的发展,直接而又广泛地影响我们的生活,促进社会的进步。
// 借用原作的话作为结尾
As computers have evolved from the room-filling behemoths that were the computers of the 1950s to the small, powerful machines of today that perform a bewildering variety of tasks, their underlying logic has remained the same. These logical concepts have developed out of the work of a number of gifted thinkers over a period of centuries....
计算机从1950年代的塞满房间的庞然大物进化到今天能够进行各种令人眼花缭乱的任务的小型超能机器,其底层的逻辑原理其实一成不变。这句话说起来简单,我却用了几年的时间才理解作者所说的一成不变到底是怎么一回事。(想起来有次跟导师聊天,他说,你看现在到处都在搞机器学习,这个状况可能还会持续一二十年然后趋于饱和,但是我们研究的东西(计算和编程语言理论)过去二十年都没有变过,未来二十年也不太可能改变,很多问题光靠机器学习是解决不了的,必须要有个deterministic的答案。)未来也许会出现新的计算模型来突破图灵机的极限,让目前看起来不可解的问题变成可解的,比如在量子计算和生物计算领域已经展露了一些理论上的可能性,we'll see.