计算机文化基础系列常识-图灵奖获奖者介绍连载(十二).doc

计算机文化基础系列常识- 图灵奖获奖者介绍连载(十二) ——非确定性有限状态自动机理论的开创者 1976 年度的图灵奖由当时在以色列希伯莱大学任教授的米凯尔, 拉宾(Michael O. Rabin) 和在英国牛津大学任数理逻辑教授的达纳· 斯科特(Dana Steward Scott) 共同获得。拉宾和斯科特是师兄弟, 两人在 20 世纪 50 年代中期先后师从著名的逻辑学家和计算机专家阿隆索· 邱奇(Alonzo Church ,他因与 Curry 一起发明了λ- 演算以及提出了“任何计算,如果存在一有效过程,它就能被图灵机所实现”这一被称为“邱奇论题”的命题而闻名于世) ,并在有限自动机及其判定问题的研究中进行合作, 奠定了非确定性有限状态自动机的理论基础。之后, 他们的研究方向不尽相同, 拉宾侧重于计算理论, 而斯科特侧重于逻辑学在计算机科学中的应用, 在各自的领域中又分别获得重大成果,作出了创造性贡献。拉宾 1931 年9月1 日生于德国的布雷斯劳(Breslau ,第二次世界大战以后成为波兰的城市并改名为弗罗茨瓦夫) 。他父亲是一名犹太教教士,也是一位博士,在当时很著名的布雷斯劳神学院教犹太历史和哲学, 还当过院长。拉宾的母亲也是知识分子, 有文学博士头衔, 年轻时即开始从事儿童文学的创作。纳粹希特勒上台以后, 拉宾的父亲因为曾经在俄罗斯呆过, 凭着政治米凯尔,拉宾(Michael O. Rabin) 达纳·斯科特(Dana Steward Scott) 敏感性,预感到会有动荡和麻烦,曾建议神学院迁往耶路撒冷,未获同意,于是全家于 1935 年迁回了巴勒斯坦,躲过了一劫。 1948 年以色列建国以后,他们成为以色列公民。拉宾在濒临地中海的港口城市海法度过了他的童年和少年时代。由于阅读了著名微生物学家保罗· 德克吕夫(Paul De Kmif) 所著的《微型猎人》一书,激起了拉宾的想象,幻想自己成为微生物学家。一次他和比他高好几班的学生比试解欧几里德几何题, 他赢了他们, 这又使他对数学产生了兴趣,因此,从莱利学院(Reali College) 毕业以后,他进入希伯莱大学学****数学, 在那里,他通过数学家克林(. Kleene ,因提出不动点定理—— theorem on fixpoint 及正则集定理一 theorem on regular set 而闻名于世) 所著的《元数学》一书首次接触到图灵关于可计算性的概念和图灵机这一理论计算模型, 立即被深深吸引。但为了打好自己的数学墓础, 他的硕土论文没有以此为课题, 而选择了当时由德国女数学家埃米· 诺特(Emmy Noether , 1882 — 1932) 创立不久的抽象代数中关于可交换环理论中的一个问题。获得数学硕士学位以后, 拉宾去了美国, 因为 20 世纪 50 年代初, 以色列建国伊始, 经济与科技都还不够发达, 很少有人研究计算这类问题, 甚至连计算机都没有。拉宾到美国后, 先在宾夕法尼亚大学, 后来转到普林斯顿大学攻读博士学位。拉宾的博士论文课题将他所熟悉的抽象代数和他感兴趣的可计算性问题联系在一起:群(GROUP) 的可计算性问题。拉宾在论文中证明了与群有关的许多问题,如群是否符合交换律等, 都是不能由计算机解答的。但是使拉宾成名的并非其博士论文而是源于 IBM 研究中