2013图灵奖获得者Leslie Lamport!

Sina WeiboBaiduLinkedInQQGoogle+RedditEvernote分享

3月18日,美国ACM协会宣布在微软硅谷研究所的Leslie Lamport获得2013年计算机界最高成就奖-图灵奖!这也是就职于微软研究所的科学家获得的第5个图灵奖!他们分别是:

Chuck Thacker (2009), Jim Gray (1998), Butler Lampson (1992) and Tony Hoare (1980)

 

其中, Jim Gray就是在2007年1月28日,在旧金山出海时失踪的数据库方面的顶尖科学家。

ACM对Lamport获奖的官方评价是:

“For fundamental contributions to the theory and practice of distributed and concurrent systems, notably the invention of concepts such as causality and logical clocks, safety and liveness, replicated state machines, and sequential consistency.”

 

这个评价很学术。大概意思是:

在分布式系统中,许多事件是离散的。Lamport同学在1978年(中国人民打倒了四人帮?)的时候,就在某一天,随意的写了一篇文章叫做“Time, Clocks, and the Ordering of Events in Pokies a Distributed System”。

从此,世界上的人们知道了什么是因果,什么是并发。。。。。

 

Lamport同学今天在得知自己获奖后,是这样的感慨的:

“During my career I have had the privilege and the benefit of working in some way with about a dozen Turing award winners, including Chuck Thacker, Butler Lampson, Jim Gray, Tony Hoare, Amir Pnueli, and Edsger Dijkstra. I feel greatly honored to have been deemed worthy of joining such a group of brilliant computer scientists.”

 

大概意思是: 终于轮到我了。。。

(1个打分, 平均:5.00 / 5)

计算的美丽--历届图灵奖获得者视频精选

(3个打分, 平均:3.33 / 5)

包云岗 。普林斯顿 。《世纪图灵纪念》

[编者注: This article is published on behalf of the author of Dr Yungang Bao。]

1912年“计算机科学之父”阿伦•图灵(Alan Turing)诞生。1930年代,计算机先驱们齐聚普林斯顿小镇,图灵、邱奇(Alonzo Church)、冯诺依曼(John von Neumann)、哥德尔(Kurt Gödel)、克林(Stephen Kleene)……。 2012年,普林斯顿大学举行了“世纪图灵纪念庆典”,邀请了20位嘉宾(包括8位图灵奖得主)介绍计算机科学的前世今生。
普林斯顿的校园里一下子多了一群耄耋老人,他们在向后人回忆当年图灵、邱奇等先驱在普林斯顿开拓计算机科学的那一幕幕往事,仿佛让人感觉回到了上世纪30~50年代那个“激情燃烧”的岁月。然而,当听到邱奇的学生80岁的斯科特教授(Dana Scott) (1976年图灵奖得主)多次黯然感慨,“这也许是我人生最后一次机会在公开场合向大家分享当年和导师邱奇一起学习、工作、生活的回忆了……”,“请再给我一个机会,我想最后再以个人身份讲一下邱奇的故事,他真是一个非常好的人,我当时就是住在他家里……”,又让人感觉到老人们似乎想在图灵百年之际向世人谢幕。此时,所有人都会安静下来,默默地聆听他们的回忆,然后报以最热烈的掌声,来表达发自内心的感动和敬意。

1. 图灵机的偶然与必然
斯科特教授是邱奇的学生,他也许是这个世界上距离那段历史最近的人了。斯科特教授的报告介绍了λ算子的过去和现在,递归函数以及图灵机之间的故事,中间不断向听众透露许多不为人知的佚事,现场气氛非常欢快。

邱奇在1930年代初提出λ算子,核心思想是“万物皆可为函数”。邱奇给出一组无类型(untyped)的函数定义规则(因为无类型而无法区分函数与参数,所以λ算子会产生递归),然后又加了几条规则,试图用函数来形式化整个逻辑系统。但后来他的学生克林发现这套逻辑系统不一致。邱奇非常失望,把整个逻辑部分全都抛掉,在1935年只把λ算子部分发表了。所以,λ算子对邱奇本人来说是一段很痛苦的经历,再也不想向其他人提及。斯科特教授说,他在普林斯顿读书的时候,从来没有听导师谈过λ算子。

1936年5月,图灵也发表了著名论文《论可计算数及其在判定问题上的应用》(On Computable Numbers, with an Application to the Entscheidungsproblem),提出了图灵机。随后图灵来到了普林斯顿大学跟邱奇读博士。这段时间,他又证明了图灵机和λ算子也是等价的。而在1936年前后,克林提出了一般递归函数(General Recursive Functions),后来邱奇证明和λ算子也是等价的。因此,图灵机、λ算子和一般递归函数都是等价的。

当时在普林斯顿高等研究院的冯诺伊曼在了解了图灵的工作后立刻意识到其重要性,他极力邀请图灵博士毕业后继续留在普林斯顿工作,但图灵非常想家,还是婉言拒绝了。随后1945年,在距离普林斯顿不远的宾夕法尼亚大学,第一台电子计算机ENIAC诞生了。但它太难操作了,人们开始寻找高效的编程方式。于是从1950年代开始,人们开始设计高级语言。1957年,巴克斯(John Backus)带领团队率先发明了第一个高级语言Fortran。与此同时,麦卡锡(John McCathy)则受λ算子启发,在1958年设计出了LISP语言。邱奇肯定不曾想过,曾经因为逻辑不一致而几乎被他抛弃的λ算子成了计算机高级语言的基础。

历史总是充满了各种巧合。在1936年以前的几千年人类文明中,人们从来没有思考过“什么是可计算的”这个问题,但在1935~1936年的一年间,却一下子提出了三种等价的理论,这岂不是太巧合了?紧随斯科特教授,来自英国爱丁堡大学的沃德尔(Philip Wadler)教授在第二个报告《邱奇的巧合》( Church’s Coincidences)一开始就提出了这个发人深省的问题。事实上,人类科技史中诸如此类的巧合比比皆是,沃德尔教授又举了好几个例子。比如,牛顿在1666年发明了微积分,而莱布尼茨在1675年也独立发明了微积分;达尔文在1859年提出进化论,而华莱士(Alfred Wallace)其实在1855年也提出了相同的理论;而贝尔和格雷(Elisha Gray)在神奇地在1876年的同一天提交了电话发明专利。

表面上历史充满了各种巧合,但如果把这些巧合放回当时的历史背景下,我们就会发现它们的出现又是必然的。今天我们将它们视为巧合是因为后人割裂了历史,只记住了少许闪光点而忽略了知识变迁过程中的幕后推手。

为了揭示图灵机巧合的必然性,沃德尔教授向听众还原了计算理论变迁的那段辉煌的历史。故事要回溯到1900年希尔伯特提出的23个数学问题,其中第2个问题是能否机械化地证明算术公理系统的一致性。1928年,希尔伯特又进一步提出了判定问题(Entscheidungsproblem),即能否找到一个算法自动地判定谓词(一阶)逻辑表达式是真还是假。1931年,哥德尔提出了不完备性定理,他构造了一个命题——“这个命题是不可证明的”,对希尔伯特的第2个问题给出了一个否定的答案。为了证明不完备定理,哥德尔写出了第一个“计算机程序”(哥德尔的程序只是用逻辑公式去形式化了几个步骤,并未定义编程规则)来验证一个命题是否能被证明。人们又从哥德尔的“程序”中觉察到希尔伯特判定问题也可能不存在答案,即没有这样的算法或不可计算。但要想证明这点,首要的是定义清楚什么是算法(或什么是有效可计算性,Effective Computability)。

全世界的数学家们都在思考可计算性定义问题,普林斯顿的数学家们也不例外。1932年,邱奇给出了第一个定义——λ算子,他本希望用λ算子来形式化逻辑系统。那时,克林正在普林斯顿大学跟邱奇攻读博士学位,也在思考可计算性定义问题。当邱奇提出λ算子后,克林发现λ算子能表示整数算术系统,这似乎是可计算性的定义了。他和哥德尔讲了这个想法,但哥德尔并不认为这定义了可计算性。克林不服,向哥德尔下了战书——如果这个定义不对,那请把你的定义拿出来,我能证明两者是等价的。1934年,哥德尔在普林斯顿高等研究院的报告中提出了一般递归函数概念。当时,刚博士毕业的克林记下了笔记。两年后(1936年),克林将一般递归函数具体化,并证明了和他之前的定义是等价的。随后邱奇又证明一般递归函数和λ算子也是等价的,并用λ算子证明了希尔伯特判定问题是不可计算的。不过“狡黠”的哥德尔还不肯承认,狡辩道,也许我的定义是错误的。

1935年的英国剑桥大学,纽曼(Max Newman)教授正在给一个关于希尔伯特判定问题的报告。他总结道,现在解决判定问题的关键就是找到可计算性的定义。23岁的图灵也在报告现场,他便开始独自思考这个问题。1936年,他发表了划时代的论文《论可计算数及其在判定问题上的应用》,用图灵机来定义可计算性(或算法),然后用图灵机重写了哥德尔在1931年的那个“程序”,也证明了希尔伯特判定问题是不可计算的。尽管图灵的证明方法比邱奇晚了几个月,但却更直观、更易于理解,而且更像一台可操作的机器。

在1936年前后的一年间提出三种完全等价的可计算性定义,都源自于希尔伯特的判定问题。到此,听众们恍然大悟又若有所思–这段经典的历史对我们又有何启发呢?我们又能在人类知识变迁历史中扮演什么角色呢?

2. 大科学(Great Science)
2000年图灵奖得主现清华大学的姚期智教授做了一场精彩的关于量子计算的报告。姚教授坦诚地说,现在自己也无法预言量子计算机何时能实用,但认为量子计算符合他定义的大科学标准。

什么是大科学?姚教授认为有两个参考标准:1)大科学是多学科交叉产生的;2)大科学伴随着颠覆性技术的出现。

姚教授举了两个例子。一个是X射线晶体学。1895年,伦琴发现X光;1912年冯-劳埃通过X衍射证明了X是波;1913年,布拉格父子提出用X射线来测晶体结构的方法;于是到了1920年代,人们开始用X射线来测金属、离子以及大分子的结构。随后人们开始讲X衍射技术应用到了生物领域,终于1950年代发现了DNA双螺旋结构,开辟了生物研究新疆界。

另一个是计算机科学。二十世纪初,希尔伯特提出数学的机械化证明。1936年图灵机出现,但只是理论模型。1945年,电子计算机发明,随后肖克利等发明了晶体管,从此计算机的运算速度便按照摩尔定律飞速发展,这是数学和半导体技术的结合。毫无疑问,这两个例子都是伟大的科学,它们彻底地改变了人们的知识和生活。

回到姚教授的报告主题,他认为量子计算正是X射线晶体学与计算机科学的结合,并举了一个非常有趣的例子。以西蒙问题(Simon’s Problem)为例,假设F(x)会将2个不同n位的0-1比特串x和s映射到同一个值,即F(x+s)=F(x),那么给定x,如何找到对应的s?传统的算法需要对F(x)进行2n次查询操作。量子计算则可以把F(x)和F(x+s)看做是两个晶体,然后用光线去照射,这样就可以根据不同的干涉条纹,然后就可以得到s。这样的操作只需要3n个光子就可以,其中的原理和用X射线衍射结果反推出晶体结构很相似。另一方面,世界各个国家都在量子计算研究投入很大的经费,量子器件的发展速度也超乎大多数人的想象。例如,目前已经有技术能实现14个粒子的量子纠缠;现在已出现传输单个光子的技术,这就意味着可以利用单个光子发送量子信号。姚教授认为,虽然很多人对量子计算表示怀疑,但从事量子计算的科学家们却要乐观的多。

姚教授做研究遵循大科学的标准,过往的经历也使他更坚信做研究应该选择有价值的问题。姚教授2004年回清华前是在普林斯顿大学开展研究工作,过去两年我很幸运有机会也在普林斯顿大学做访问博士后,所以这里的科研价值观,我也有些体会。在普林斯顿,很多教授和学生都非常自信,认为只要他们决定去做一件事,就一定能做好。另一方面大家又意识到,做一件琐屑的小事,所花的精力其实并不比有价值的大事少。因此,在这种自信心和价值观的支持下,他们就敢于去尝试一些很有挑战的问题,有时甚至会跨很大的方向。

李凯教授的研究经历就是一个很好的例子。他博士工作首次提出了软件分布式共享内存(Distributed Shared Memory,DSM)思想,到普林斯顿后又做了硬件共享内存系统SHRIMP,之后研究用多个投影仪组成可扩展显示墙(Scalable Diaplay Wall),后来又转到研究基于内容的多媒体搜索技术。而创办Data Domain公司时则进入存储领域,研制出世界上第一个数据冗余存储产品。如今,他和脑科学领域专家合作,开展脑科学计算的前沿研究。虽然不是所有的项目都像DSM和Data Domain那样成功,但通过开展这些有挑战的项目,积累了许多高质量论文(h-index为64),培养了不少出色的人才,也在同行中建立了学术威望。

3. “定义”的力量
2010年图灵奖得主哈佛的瓦伦特(Leslie Valiant)教授介绍了他对计算机科学的独特观点,并回顾了他的研究历程。瓦伦特教授是机器学习的鼻祖。上世纪七八十年代,人工智能还是以构建专家系统为主。专家系统的思想就是通过建立大量规则来指导计算机推理,但很快便发现人工建立规则是一件非常艰难的任务。当研究人员一筹莫展时,瓦伦特教授提出让计算机自己学习规则的思想,成为数据挖掘和机器学习奠基性的工作。

机器学习并不是我的研究领域,所以了解并不多。但瓦伦特教授的报告充满了想象力,给我很多联想和启发。他认为图灵不仅仅是一位数学家、计算机科学家,更像是一位自然科学家,而计算机科学也可看作是一门自然科学。他在幻灯片上摘出了图灵1948年的论文《智能机器》(Intelligent Machinery)中一段话,“… genetical or evolutionary search by which a combination of genes is looked for, the criterion being survival value.”,然后说图灵所思考的已经超越了计算机科学,可以归到自然科学范畴了。报告中,他又说道其实机器学习的必要性和意义图灵早就在1948年就指出来了,许多听众感到有些茫然。只见瓦伦特教授翻到一页幻灯片,又摘出了图灵那篇《智能机器》 中的一段文字,其中有这么一句话“the learning of languages would be the most impressive”。瓦伦特教授稍加解读,众人顿时恍然大悟,不禁感慨图灵真如神一般高不可及,而学术大师们则像神父一样能读懂神的思想,向世人传达神的指示。

瓦伦特教授的报告中提到好几个有趣的定义,比如什么是学习,什么是进化。这些高度抽象的概念,瓦伦特教授却能用数学进行漂亮的形式化定义,令人叹为观止。很多难题无从下手时,正是因为问题没有定义清楚,而巧妙的定义经常另辟蹊径,帮助人们找到解决问题的关键。有个笑话从反面诠释了定义的能量。一位哲学教授将一把椅子提到讲台上,对学生们说,今天哲学课考试题目是–证明这把椅子不存在。学生们开始冥思苦想,但只过五分钟有位学生即交卷了。教授一看,答卷上只有五个字,但连声称绝,打了满分。这五个字是——"什么是椅子?"

这让我联想起在普林斯顿时与李凯教授的一次讨论。当时,我们希望对比两个程序行为是否相似,这听起来也是一个无从下手的问题。于是李凯教授让我先去定义“什么是程序行为?、“什么是相似?”当我把这些问题定义清楚后,解决思路就明确了。这次经历也让我深刻体会到只有将问题定义的越清晰,才能找到明确的解决方法。

如果说好的定义是解决问题的关键,那伟大的定义往往开辟新的领域。这样的例子在计算机科学发展史上比比皆是。除了瓦伦特教授定义了什么是学习开创机器学习领域外,还有图灵用图灵机定义了什么是可计算,开创了整个计算科学领域;香农(Claude Shannon)通过不确定的概率定义了什么是信息,开创了信息论;里维斯特(Ron Rivest)等通过概率上的不可区分性(indistinguishability)定义了什么是安全,开创了计算机时代的安全领域。

4. 互联的未来
纪念活动的高潮是普林斯顿校友,Google前CEO、现Google董事会主席斯密特(Eric Schmit)的报告,可容纳400人的报告厅座无虚席,甚至有人坐在台阶上。

斯密特报告的主题是未来,他给现场听众描绘了一幅美好的未来蓝图。未来智能手机将越来越便宜,如今已经有几十美元的Andriod手机了。未来的市场主要会在发展中国家,如今中国、印度每年智能手机都是以几千万的速度在增长,而非洲国家也会成为新兴市场。未来将会有30亿新网民加入到互联网,这蕴含着巨大的应用需求,同时也带来巨大的创造力。斯密特还畅想了一系列新兴应用,比如无人驾驶汽车、穿戴式设备等。

报告结束后留了半个多小时提问,大家非常踊跃。有人问Google是否能帮助设立诺贝尔计算奖,Google的数字货币计划是什么,未来该如何学习快速发展的技术,互联世界和现实世界的区别,Google在如何帮助发展中国家,还有人提问请斯密特给本科生一些建议…… 我也起身问了一个关于Google X实验室的问题,并开玩笑式的问怎么才能进Google X实验室。斯密特说,有人泄露Google X的信息,Google X实验室细节仍然是机密,所以他可以透露无人驾驶汽车项目,但不能再说更多其他的项目,不过请想象一下Google X的研究人员正在整合计算机科学、硬件和新设备,那也许会对Google X有一些感觉。事实上,Google X确实很秘密,存在好多年而不为人所知,即使是Google员工。直到2011年11月纽约时报泄露有关信息,外界才得以了解。Google X项目都是非常激进,比如无人驾驶车、Google 眼镜、机器人巡逻队、甚至太空电梯。上期CCCF刊登的CACM译文《谷歌的混合研究方法》(Google’s Hybrid Approach to Research)中提到工程与研究并重的混合研究模式会更倾向于低风险的短期项目,而专注长远影响的Google X实验室则是对混合模式的补充。

斯密特提到的很多观点和我最近读的戴曼迪斯(Peter Diamandis)的《Abundance:The Future Is Better Than You Think》一书中很多观点一致。事实上,斯密特和戴曼迪斯本来就是私交很好的朋友,他们甚至最近和Google的创始人佩奇(Larry Page)、《阿凡达》导演卡梅隆(James Cameron)一起宣布创办了Planetary Resources公司,目标是太空采矿!

斯密特和戴曼迪斯对未来的判定并不是凭空臆想。如果跳出某项具体技术,从更广阔的时空来观察技术本身的发展,就会发现技术发展也有规律。比如,笔者之前在CCCF上刊登的《谁推动信息产业发展》文章中引用了美国科学院的一份报告,该报告分析了19个计算机技术的发展史,从而得出基础研究与产业化互动的一些规律。而《Abundance》一书给读者呈现了另一条有趣的规律——产生巨大影响的技术都是指数发展型技术(Exponential Technologies)。

在科技史上有很多成功利用这条规律预测未来的例子。例如1953年美国空军分析了从1911年飞机发明到1953年之间飞机加速技术发展曲线,发现飞行器发动机的加速度增长是指数发展的,并预测1970年左右人类便能登上月球。这个判断是在1953年做出来的,这在当时是难以想象的,因为最乐观的估计也认为登上月球至少还需要50年(2000年左右)。

而摩尔定律是计算机领域都熟知的另一个例子。1965年摩尔(Godern Moore)在一篇文章中用1959年到1965年的5个点画出了一条直线,并成功预测未来10年(到1975年)半导体技术的发展趋势,即单个芯片晶体管数目将每12个月翻一番(后来修正为每18个月)。一个又一个十年过去了,摩尔定律在过去的50年里都有效,并还会持续到至少2020年。

从技术层面上去判断一项技术是否为指数型技术需要极远的眼界和很深的造诣,往往只有摩尔这样的大师才能做到。我的一个观点是,技术的成本也许是一个简单有效的判断依据,即在相同的性能下价格是否在不断下降,或在相同的价格下性能是否在不断提高?当然技术的潜力还依赖于市场饱和度。所以,综合技术成本和市场饱和度两方面的因素来看,智能手机和互联网确实还有很大的潜力,尤其是中国广大的农村市场和其他发展中国家。

5. 结语
2012年即将过去,世界各地的图灵纪念活动也都逐渐落下帷幕。这些纪念活动让我们这些和图灵本没有时空交集的晚辈也能感受那个造就伟大图灵的时代,这是一个伟大的时代,希尔伯特,邱奇、哥德尔、冯诺依曼……
那我们所处的时代是伟大的时代吗?图灵知道他所处的时代是伟大的吗?图灵已逝,我们不得而知。但我有一个猜想,也许哥德尔不完备定理的第二点(公理系统的一致性不能在其内部被证明)也适用于历史系统——历史舞台上的扮演者无法证明自己所处的时代是伟大的。

(11个打分, 平均:4.91 / 5)

计算的美丽–2011图灵奖获得者Judea Pearl

2012年3月15日,2011年的图灵奖获得者揭晓【ACM新闻稿】。UCLA计算机系的Judea Pearl荣获此计算科学界的最高殊荣。

ACM对Judea Pearl获得2011年图灵奖的官方评语是:

Developed Novel Framework for Reasoning under Uncertainty that Changed How Scientists Approach Real World Problems

【编者译】授予Dr. Judea Pearl图灵奖,以表彰其在模糊和不确定性推理,统计人工智能方面的贡献。其工作深刻的帮助了相关领域的科学家们如何研究和解决现实复杂问题。

Judea Pearl,生于1936年,犹太人,美国籍科学家。Judea Pear于1960年毕业于 以色列理工学院Technion。1974年从NYU Polytechnic获得其电子工程的博士学位。目前是UCLA计算机系认知实验室的终身教授。

Judea Pearl在人工智能,机器推理方面最大的贡献是把统计模型的引入。“Before Pearl, most AI systems reasoned with Boolean logic—they understood true or false, but had a hard time with ‘maybe.’””。Judea Pearl提出概率和因果性推理演算法,彻底改变了人工智能最初基于规则和逻辑的方向。其著作《Causality:Models,Reasoning,and Inference》创立了因果推理演算法,并因此获得了2011年英国伦敦经济和政治科学学院的Lakatos奖,评语中说“他为科学哲学作出了重大的杰出贡献”。

Judea Pearl通过在智能系统不确定的问题空间里,应该概率统计模型,为人工智能的发展开辟了一个具有实际意义的重大方向。超出了经典的基于逻辑理论基础的人工智能以及基于规则科技的专家系统范畴。


(1个打分, 平均:5.00 / 5)

Reflections on Software Research–关于软件研发的反思

(1个打分, 平均:5.00 / 5)

随风而逝:Dennis Ritchie大师10月8日离世

Dennis Ritchie,全名Dennis MacAlistair Ritchie, 用户名dmr,照片见上左图。
生卒年月与地点: 1941年9月9日生于纽约州Bronxville,2011年10月8日卒于新泽西Murray Hill,享年70岁
工作单位:贝尔实验室
毕业学校:哈佛大学,学士(1962年),博士(1968年)
毕业专业:物理学,应用材料学
退休时间和最后职务:2007年,朗讯贝尔实验室系统软件研究部主任

从业领域:计算科学

主要发明:C语言,Unix操作系统(与Ken Thompson共同发明)

主要著作:
1. Unix Programmer’s Manual (1971)。就是今天Unix系统中打“man”出来的文字。
2. The C Programming Language (1978年出版,与Brian Kernighan合著,见上图中,此为1978年第一版的封面)。 此书在学术界有著名的昵称K&R,取两作者姓氏第一个字母而得。

主要荣誉:
1983年,ACM图灵奖(Turing Award),与Ken Thompson共同获得,获奖理由:”for their development of generic operating systems theory and specifically for the implementation of the UNIX operating system. Ritchie的图灵得奖报告主题是”Reflections on Software Research.”

1988年,当选美国国家工程院院士,贡献为”development of the ‘C’ programming language and for co-development of the UNIX operating system.”

1990年,IEEE汉明奖(Richard W. Hamming Medal),与Ken Thompson共同获得,获奖理由:”for the origination of the UNIX operating system and the C programming language.”

1999年:获得1998年度美国国家科技奖章(National Medal of Technology),与Ken Thompson共同获得,颁奖人:比尔克林顿,见上右图。获奖理由:”for co-inventing the UNIX operating system and the C programming language which together have led to enormous advances in computer hardware, software, and networking systems and stimulated growth of an entire industry, thereby enhancing American leadership in the Information Age.”(共同发明了Unix操作系统和C程序语言,推动了计算机硬件、软件和网络系统研究的卓越进展,并由此带来了一个全新的产业,确保了美国在信息时代的领先地位)

====================
用户dmr最后一次登录时间已经定格。弯曲评论愿Dennis Ritchie大师一路平安,不知道天堂里有没有操作系统?
/* Dennis Ritchie Rest in Peace and Thank You! */

(11个打分, 平均:5.00 / 5)

计算的美丽–2010图灵奖获得者Les Valiant

2011年3月7日,2010年的图灵奖获得者揭晓【ACM新闻稿】。哈佛大学计算机系的Les Valiant荣获此计算科学界的最高殊荣。

ACM对Les获得2010年图灵奖的官方评语是:

“For transformative contributions to the theory of computation, including the theory of probably approximately correct (PAC) learning, the complexity of enumeration and of algebraic computation, and the theory of parallel and distributed computing.”

【编者译】授予Dr. Les Valiant图灵奖,以表彰其在计算理论方面,特别是机器学习领域中的概率近似正确理论的开创性贡献,枚举和计算代数复杂性,并行和分布式系统方面的其他贡献。

Les Valiant,生于1949年3月28日,英国科学家。1974年从University of Warwick获得其计算机科学的博士学位。目前是哈佛大学计算机和应用数学系的教授。

Les在计算理论方面最大的贡献是Probably approximately correct learning。PAC的意义大概如下:该模型可解决信息分类的问题,比如判断一封邮件是不是SPAM。为解决信息分类问题,学习算法会根据过去的经验而设计一个概率假设,并将此假设作为判断依 据。然而,这种根据过去经验的泛化可能并不适用于将来,比如过度泛化。PAC模型可最大限度地降低泛化带来的错误,这就是为什么它被称为“概率近似正确” 的原因。此学习模型对于机器学习、人工智能和其他计算领域(如自然语言处理、笔迹识别、机器视觉等)都产生了重要影响。

除计算机复杂性理论之外,Valiant还为并行计算和分布式计算作出了重要的贡献。

在过去的几年内,Valiant还致力于计算神经学的研究,他为大脑设计了一个数学模型,并将此它与复杂的认知功能建立了关联。此发现发表在《Circuits of the Mind》一书中。

(4个打分, 平均:5.00 / 5)

2009图灵奖-Charles P. Thacker

2009年的图灵奖在2010年3月9号揭晓,获奖者是Charles P. Thacker. 获奖理由是他设计并且实现了第一台个人计算机以及网络计算机的原型Alto. 原文是 “for his pioneering design and realization of the Alto, the first modern personal computer, and the prototype for networked personal computers.” 图灵奖就本身就不要介绍了,上弯曲的读者都应该知道这个奖. 图灵奖的奖金是25W美金,由Intel和Google赞助.我记得之前图灵奖的奖金是10W美金,由Intel独家赞助.什么时候涨价了?

本人虽然尊重图灵奖,但是对 图灵奖并没有太深的兴趣,为什么呢?因为图灵奖的获奖人员搞的研究都比较学究.本人只是一个穷工程师而已,因此,对于太学究的研究不太感兴趣(但我很尊重从事这方面的研究人员,比如号称精通形式语言的陈首席).但是这次对于Charles P. Thacker能获得图灵奖我还是很高兴的.因为Charles从事的是我感兴趣的研究计算机体系结构.

Charles赖以获奖的Alto是由他1973年在施乐帕克(Xerox PARC)研究中心的时候年设计制造.之所以说它是第一台个人电脑是因为它已经具有PC的一般特征.Alto具有显示器,鼠标,键盘.硬盘,GUI以及 以太网连接(厉害吧). 可惜的是当时施乐帕克研究中心并没有意识到它的商业价值,从而Alto的新颖设计沦为为他人(Apple)作嫁衣的角色. 据说后来 Steve Jobs访问PARC的时候,被Alto的一些设计所吸引,随后这些设计被用在了苹果的Macintosh computer中,比如鼠标,GUI.等到PARC醒悟的时候,为时已晚,市场已经发生了变化. 另外,以太网的技术后来被licence给了3COM,而后者则成为网络设备领域重要的厂商. 虽然Alto没有取得商业价值,但是其孵化出来的技术却影响了后来的个人计算机,以及成就了其他公司。从人类整个财富的角度来说,贡献还是大大的.

在1983年,Charles Thacker离开了PARC,并作为创办人之一创办了DEC SRC(System Research Center)(SRC是的leader是 Robert Taylor, 原先也在PARC供职,因为内部权力斗争离开了PARC从而创办SRC.也许Charles也想离开PARC,因此和Robert Taylor一拍即合).Charles在SRC的经历也验证了牛顿第一定律,sorry,笔误,是牛人第一定律:牛人在什么地方都是牛的.除了Alto,实际上他在计算机体系结构和网络方面也颇有建树.在 SRC,Charles领导了第一台多处理器工作站Firefly和第一个Alpha架构的多处理器Alpha Demonstration Unit的开发. 并且它的研究团队设计出了AN1(Autonet)以及AN2,后者后来成为了DEC的Gigabit/ATM产品.

1997年 Charles加入了微软,目前Charles在微软从事计算机体系结构的研究.既然Charles能获得图灵奖,在之前肯定是有其他奖来铺垫的. 在此前获得的重量级的奖项有2004年获得的查理· 斯塔克· 德雷珀奖(Charles Stark Draper Prize)((2009年诺贝尔物理学奖获得者高锟1999年获得此奖).)和2007年获得的IEEE John von Neumann Medal.

当然了,我们老中也不必为不能获得图灵奖还懊恼,毕竟咱们起步晚.人家在73年玩计算机的时候,我们还在玩人呢.也许再过N年,图灵奖获得者能出现中国人的名字.另外有志冲击图灵奖的各位同学们,一定要勤锻炼身体,把身体弄的健健康康的。因为Charles在设计了Alto将近40年后才获奖的经历告诉我们,即使你有获奖的才能,也得有机会活着领奖才行。:)


(3个打分, 平均:5.00 / 5)

我与Jim Gray的一段交往

image       今天偶然在网上看到一些有关Jim Gray的新闻,使我想起多年前的一段往事。Jim于2007年在旧金山湾区附近,孤身驾船出海去抛洒他母亲的骨灰,就此人船同时失踪,至今音信全无。Jim是数据库技术的奠基人(Transaction概念发明人),并因此获得图灵奖。他1969年获得伯克利计算机博士,是伯克利的第一位计算机博士,曾经在IBM,DEC,Tandem,和微软从事研究工作。这里我就写下这段小文,回忆我与他的一段交往,和由此引起的一次微软面试,以此纪念Jim Gray先生。

      根据我在计算机技术行业(和学术界)混迹多年的经验,在技术上没有刷子的人,基本上比较友善;有一、两把刷子的人中,颇有一些人自我感觉很好,牛X哄哄;但是真正到了技术顶级大牛、有许多把刷子的人,又是非常友善,平易近人。与Jim打交道的经历再一次验证了这一点。

      时光如梭,算来这已经是将近十年前的事了。那时我还在学校读书,寒窗数载,正处于毕业答辩和要找工作糊口的关头。可惜当时正是Internet泡沫消失,股市崩盘之时,各大公司都在忙着裁人,并不招人。我老板出主意说,你论文做得不错,不如去学术界吧,做大学教授多牛。我说行,咱就这么定了。说说容易,大学的坑就那么几个,想填坑的萝卜倒是不少,尤其是当时工业界不招人,刚毕业的萝卜们纷纷转向学术界,可谓“萝卜年年有,今年特别多”。

      有一天,就在我在实验室忙着修改简历时,老板带来一个人,很是高大魁梧,络腮胡子。老板说,这位是微软的Jim Gray,你来接待一下,介绍一下我们实验室的研究。我说行,这位同学是谁,做什么方向,那位同学是谁,做什么题目。然后开始聊我做什么,Jim对我做的项目很感兴趣,提出能不能把我的毕业论文Email给他一份,我说没问题。又说起我正在找工作,他说我在微软上班,你有没有申请?我说微软听说过,但没申请,我现在是主攻Academia。他说应该申请一下,我来给你做推荐,我说那敢情好,行。

      Jim离开实验室后,我就给他发了一份Email(CC给我老板),附上我的论文,具体怎么写的我已经忘了,只记得说希望这个论文对你能“Helpful”。不想老板很快就回信(CC给Jim),说您这位同学,有没有搞错? 英语还要继续学习,你的破论文还能对Jim Gray “Helpful”?Jim抽空看你的论文,不但是你的光荣,那也是我的光荣。

      我一想,这怎么回事儿?我老板在学术界也算个人物,当年只用两年就拿下Berkeley博士学位,八十年代就是IEEE Fellow,平时喝两杯之后也是谁都不忿(他好像就服两个人,Dijkstra和Knuth),今儿这是怎么啦?这位Jim Gray是何许人也?我网上查了一下,那天又去听了Jim的一个Talk(好像是关于Worldwide Telescope的),才发现此公来头不小。刚才咋就没看出来呢?

      赶紧给老板回Email,您老说的太对了,我的英语确实需要继续学习。从此记住了“helpful”这个词不能乱用。后来Jim回Email说,哈哈,没关系,Helpful=Informative。他还真把我的论文认真看了一遍,并交换了几封Email,讨论一些有关技术细节。我记得,当时有感于论文中背景引用的全是洋人的工作,我天朝上国在计算机方面确实没什么可引用的,我就在前言中加上了一页《道德经》(和英文翻译),用“大象无形,大音希声”的道理蒙鬼子一把。所以,Jim回信中还提到,你论文中提到的“Tao”很有意思,我说,那是,这可是我天朝的学术瑰宝,那学问可大了去了。他说,是,是,Tao的英文版我学习过多次。

      后来,我就给微软发了一份Job Application,微软的人事部也特痛快,效率很高,不久就回信说,来信收到,多谢申请,目前没有对您合适的位置,不是你不好,是我不好,以后有合适的再联系,等等Bulls__t。到此完了也就完了,奇怪的是,几小时后,我又收到微软一封Email,说误会误会,有位置,我们来安排一个Phone Interview怎么样?

      在Phone Interview时我才明白,该同学开始没看到Jim的推荐信,后来看到后,马上就有位置了。Phone Interview他就问了两个脑筋急转弯的问题。一个说,我三个筐子,一个装苹果,一个装橙子,一个装苹果和橙子。你看不到筐子里的东东,而标签都贴错了,你只能任选一个筐子,拿一个水果出来,然后把标签都改正过来,怎么拿? 还有一个问题是,屋子里有三盏灯,屋外有三个开关,屋外看不到屋里。你在屋外可以任意设置三个开关,然后进屋一次,就要说出哪个开关控制哪盏灯。怎么办?那时候我还年轻,反应还不慢,折腾了大概二十分钟,把两个问题都答上来了。

      该人事同学说,很好很好,我马上安排下一步Interview。过了几天,他说你申请的是“Software Design Engineer”,目前不招人,有一个“Software Test/Design Engineer”可不可以,做得好以后可以改成Design Engineer。一般来说,在当时的工作市场的大背景下,这也就不错了。可惜我当时在学校念书久了,基本处于不知道自己吃几碗干饭的状态。我想我Phone Interview答得好,又有Jim Gray的推荐,这不行,不考虑。他说,你可想好了,过了这村就没这店了。我说,想好了,不要。

      几天无话。可能是Jim在微软的影响不小,几天后,该同学又来电话了,说有位置了,就是“Software Design Engineer”,你来西雅图面试吧。我说行,你掏钱要我去Seattle逛逛,干嘛不去。为此我还推掉了去东部一所学校的面试,搞得对方不太愉快,我买好的机票也就没人给报销了。在以后的几个星期,我从网上下载了大量的微软的面试题,都是Brain Teaser一类,不外乎大桶装五升水,小桶装三升水,中桶装多少水?张三戴红帽子,李四戴绿帽子,王老五带什么帽子?

      在我成为解答“王老五戴绿帽子”之类问题的绝顶高手后,飞往Redmond微软Campus面试,去后才发现这类问题人家压根儿就没问。不仅如此,我还被那位人事同学给害了,他给我安排面试的是Windows Kernel Group(你丫不是牛吗,到Kernel Group试试吧)。微软有几万人,但开发Windows Kernel就这么九、十个人,每个人看起来都不同凡响,神神叨叨的。一位老哥对我说,看见旁边这个大黑盒子了吧,我正在那编译整个Windows呢,要编一整天时间。要搁现在,我会说,这有什么好吹的,有病啊?那时不一样,还是学生,呦,Windows我倒是天天用,就是没编译过,您老牛啊!那是,我老当然牛,但编程也有错误,这不,这刚有个Bug我终于找出来了,你来看看,错在哪?这个,写得好,没错啊? 再看看!写的确实好,真的没错啊?这都看不出来,那是你脑袋不好使,笨啊!这不,这块内存太大了,把那一块给覆盖了。没错,这我哪看得出来?还有一位,说这有一个题目,马上把程序写在黑板上,不能有编译错误,要处理所有error code。写完以后,他说,基本可以,但这两个error没有处理。就这样几轮过后,我就感觉形势不太妙。晚上,和一位微软的和其他几位面试一起吃大餐,微软买单。和几位一聊,发现他们都被问到水桶装水之类的问题,就我没有,估计是面试我的几位不屑问这种问题,很是郁闷。

      回来以后,微软还是效率很高,不久就来信说,多谢你来面试,感觉目前的位置和您不match,不是你不好,是我不好,以后再联系。嘿,你不要我,我还懒得去你那一年九个月下雨的鬼地方!此处不留爷,自有留爷处,处处不留爷,爷去投八路。几个月后,我就打点行装,离开加州,去东部一所学校教书了。

 

注: Jim Gray在微软的工作是在Microsoft Research Bay Area Center, 其中有多个计算机界的顶尖人物,例如,分布式计算的开山鼻祖Leslie Lamport(也是LaTex的最初开发者。个人意见,该同志完全有资格拿一个图灵奖)也在那。 有关Jim的详细介绍,可参见怀临的“计算的美丽”,或下面的页面:

计算的美丽–1998年图灵奖获得者James Gray

Jim Gray – Wikipedia

Jim Gray – Microsoft Research

(10个打分, 平均:4.80 / 5)

中国计算机科学2020研讨会 。科学家名单

谁能数据挖掘出2009年10月在清华大学的中国计算机科学2020研讨会中,姚期智邀请来的14位科学家名单和其详细背景?天下除了《弯曲评论》,存在第二家的可能性就像下面理论计算科学家研究的不确定问题一样,基本上是不可在多项式时间算法下求证。除非拿出反例(certificate),断言可以但很难证伪:-)。

1. 哈佛大学教授、1976年图灵奖获得者、美国国家科学院院士Michael O. Rabin。演讲题目:Privacy and Secrecy in the Age of the Internet and Search Engines

2. 伯克利加州大学教授、1985年图灵奖获得者,美国国家科学院院士,美国国家工程院院士Richard M. Karp。演讲题目:What Makes an Algorithm Great?

3. 康奈尔大学教授、1986年图灵奖获得者,美国艺术与科学院院士,美国国家科学院院士John E. Hopcroft。演讲题目: Future Research Directions in Computer Science

4. 卡内基梅隆大学教授,1994年图灵奖获得者Raj Reddy。创新工场老总李开复在CMU时候的博士导师。 演讲题目:Technology in Service of Society

5. 卡内基梅隆大学教授,2007年图灵奖获得者Edmund Clarke。 演讲题目:Model Checking: My 28-year Quest to Overcome the State Explosion Problem

6. 伯克利加州大学教授、美国艺术与科学院院士、美国国家工程院院士、美国国家科学院院士Christos Papadimitriou。 演讲题目: The Algorithmic Lens: How the Computational Perspective is Changing the Sciences。

7. 卡内基梅隆大学教授、美国艺术与科学院院士Jeannette Wing。 演讲题目:Computational Thinking and Thinking About Computing

8. 伯克利加州大学教授、美国工程院院士,美国科学院院士David Patterson。 演讲题目:Your Students Are Your Legacy

9. 麻省理工学院教授、美国艺术与科学院院士、美国国家工程院院士、美国国家科学院院士Silvio Micali。 演讲题目: New Mechanisms for A New World

10. 斯坦福大学教授,麦克阿瑟奖获得者Daphne Koller。 演讲题目:Probabilistic Models for Holistic Scene Understanding

11. 普林斯顿大学教授Sanjeev Arora。 演讲题目:Computer Science: A New Way to Think

12. 普林斯顿高等研究院Avi Wigderson。 演讲题目:Randomness – A Computational Perspective

13. 美国能源部Argonne国家实验室高级院士Charlie Catlett。 演讲题目:The Personal Digital Augmenter and Buffer Overflow in Humans

14. 匈牙利罗兰大学教授Laszlo Lovasz。 演讲题目:Large Networks: A New Language for Science

【附录:对计算机界图灵奖获得者有兴趣的读者,可以参阅】

《计算的美丽–图灵奖的第一个四十年》(上)

《计算的美丽–图灵奖的第一个四十年》(下)

(2个打分, 平均:5.00 / 5)