米凯尔·拉宾 - 导语

——非确定性有限状态自动机理论的开创者

1976年度的图灵奖由当时在以色列希伯莱大学任教授的米凯尔，拉宾(Michael O．Rabin)和在英国牛津大学任数理逻辑教授的达纳·斯科特(Dana Steward Scott)共同获得。拉宾和斯科特是师兄弟，两人在20世纪50年代中期先后师从著名的逻辑学家和计算机专家阿隆索·邱奇(Alonzo Church，他因与Curry一起发明了λ-演算以及提出了“任何计算，如果存在一有效过程，它就能被图灵机所实现”这一被称为“邱奇论题”的命题而闻名于世)，并在有限自动机及其判定问题的研究中进行合作，奠定了非确定性有限状态自动机的理论基础。之后，他们的研究方向不尽相同，拉宾侧重于计算理论，而斯科特侧重于逻辑学在计算机科学中的应用，在各自的领域中又分别获得重大成果，作出了创造性贡献。

米凯尔·拉宾 - 个人简历

拉宾1931年9月1日生于德国的布雷斯劳(Breslau，第二次世界大战以后成为波兰的城市并改名为弗罗茨瓦夫)。他父亲是一名犹太教教士，也是一位博士，在当时很著名的布雷斯劳神学院教犹太历史和哲学，还当过院长。拉宾的母亲也是知识分子，有文学博士头衔，年轻时即开始从事儿童文学的创作。纳粹希特勒上台以后，拉宾的父亲因为曾经在俄罗斯呆过，凭着政治敏感性，预感到会有动荡和麻烦，曾建议神学院迁往耶路撒冷，未获同意，于是全家于1935年迁回了巴勒斯坦，躲过了一劫。1948年以色列建国以后，他们成为以色列公民。

拉宾在濒临地中海的港口城市海法度过了他的童年和少年时代。由于阅读了著名微生物学家保罗·德克吕夫(PaulDeKmif)所著的《微型猎人》一书，激起了拉宾的想象，幻想自己成为微生物学家。一次他和比他高好几班的学生比试解欧几里德几何题，他赢了他们，这又使他对数学产生了兴趣，因此，从莱利学院(RealiCollege)毕业以后，他进入希伯莱大学学习数学，在那里，他通过数学家克林(S．C．Kleene，因提出不动点定理——theoremonfixpoint及正则集定理一theoremonregularset而闻名于世)所著的《元数学》一书首次接触到图灵关于可计算性的概念和图灵机这一理论计算模型，立即被深深吸引。但为了打好自己的数学墓础，他的硕土论文没有以此为课题，而选择了当时由德国女数学家埃米·诺特(EmmyNoether，1882—1932)创立不久的抽象代数中关于可交换环理论中的一个问题。获得数学硕士学位以后，拉宾去了美国，因为20世纪50年代初，以色列建国伊始，经济与科技都还不够发达，很少有人研究计算这类问题，甚至连计算机都没有。拉宾到美国后，先在宾夕法尼亚大学，后来转到普林斯顿大学攻读博士学位。拉宾的博士论文课题将他所熟悉的抽象代数和他感兴趣的可计算性问题联系在一起：群(GROUP)的可计算性问题。拉宾在论文中证明了与群有关的许多问题，如群是否符合交换律等，都是不能由计算机解答的。

米凯尔·拉宾 - 学习研究过程

但是使拉宾成名的并非其博士论文而是源于IBM研究中心于1957年向他和他的师弟斯科特提供的一份暑期工作。公司允许他们作他们感兴趣的任何工作，于是拉宾和斯科特就联手研究有限状态自动机(finitestateautomata，缩写FSA)。前人在研究这种机器时的基本信条是：机器在输入相同时，其“心智状态”也相同，即对于具有给定指令集的机器而言，一定输入的机器总是按同一方式运行的。拉宾和斯科特认为，这种具有“确定性”行为的机器带来了局限性。因此，他们定义了一种新的、“非确定性”的有限状态自动机(nondeterministicfinitestateautomata，缩写为NDFSA)，这种机器在读取到一定的输入后，有一个可以进入的可能的新的状态的“菜单”可供选择，这样对给定的输入计算便不单一了，每个选择代表一种可能的计算。拉宾和斯科特将图灵的有限状态自动机从确定性一种形态扩展到非确定性的另一种形态，极大地推动了有限状态自动机理论的发展。虽然非确定性有限状态自动机的能力并不比确定性的有任何增加(拉宾和斯科特自己已经证明任何可以用非确定性机器解决的问题都可以在确定性机器上解决，而且提出了将非确定性机器转换为确定性机器的方法问题)，但是它可以简化机器描述和加快解题速度。后来的实践证明，非确定性有限状态自动机在机器翻译、文献检索和字处理程序等应用中都起了重要的作用。拉宾和斯科特的研究成果过了两年才在IBM公司的研究和开发杂志上发表，这就是论文“有限自动机及其判定问题”(Finiteantomataandtheirdecisionproblems，IBMJournalofResearchandDevelopment，3(1959)，114—125页)。

米凯尔·拉宾 - 参考文献

ACM图灵奖(1966-2001增订版计算机发展史的缩影) 吴鹤龄，崔林编

参考资料：

1 http://www.math.org.cn/forums/index.phpshowtopic=45808

2 http://deercrane.spaces.live.com/blog/cns!8BEF692B75EB8095!221.entry