米凯尔·拉宾-图灵奖获得者- 科技百科 -互联网博物馆，你我的知识加油站

迈克尔·O·拉宾（Michael Oser Rabin，希伯来文：מִיכָאֵל אֹשֶׁר רַבִּין‎ ）是一名以色列计算机科学家，1976年图灵奖得主。曾在算法开发领域中扮演过中心人物的角色，他的关于随机算法，即有非常非常小的出错可能性，但却是十分有效的算法，引发了密码技术和网络计算开发中的大量成果。

[显示部分][显示全部]

个人简历和资料编辑本段 回目录

迈克尔·拉宾

迈克尔·拉宾1931年9月1日出生于德国的布雷劳斯（二战后成为波兰弗洛兹瓦夫），父亲是一个拉比。1953年，他获得希伯来大学的理学硕士，1956年获普林斯顿大学博士学位。

1959年，拉宾和达纳·斯科特共同发表了“有限自动机与其判定性问题”（Finite Automata and Their Decision Problems）的论文，提出了非确定自动机的观点。他们也因此获得了1976年的图灵奖，并做“计算机复杂性”（Complexity of Computations）的演讲。图灵奖的引文是：

“因他们的合著论文“有限自动机与其判定性问题”。论文中引入了非确定自动机的概念，被证明是（计算理论科学研究中的）一个非常重要的概念。拉宾和斯科特的这篇经典论文成为了这个领域后续研究的源泉。”

非确定自动机已经成为计算复杂度理论中的一个重要概念，特别是在描述P与NP问题的复杂度类时。

1969年，拉宾证明N successors的二阶逻辑是可判定的。[证明的关键部分暗示了parity game的确定性。1975年，拉宾发明了米勒-拉宾检验，这是一个相当快速的随机算法（有较小的可能性错误），用于判断一个大数是否是素数。快速素数检验是目前大部分公钥密码体系的关键。1979年，拉宾发明了第一个非对称密码系统——拉宾密码系统。它的安全性被证明和整数因式分解的复杂度相同。1981年，拉宾提出了不经意传输（oblivious transfer）技术。 1987年，拉宾和理查德·卡普提出了一个著名的字符串搜索算法——拉宾-卡普算法。

出生 1931年9月1日 (1931-09-01) （77岁）

迈克尔·拉宾

出生地德国魏玛共和国布雷斯劳（今波兰弗罗茨瓦夫）
研究领域计算机科学
著名成就米勒-拉宾素数检验
拉宾密码系统
不经意传输（Oblivious transfer）
拉宾-卡普字符串搜索算法（Rabin-Karp string search algorithm）
非确定有限状态自动机
研究机构哈佛大学
希伯来大学
哥伦比亚大学
获奖图灵奖

获得奖项与荣誉编辑本段 回目录

the ACM Turing Award in Computer Science,
the ACM Kanellakis Theory and Practice Award,
the Rothschild Prize in Mathematics,
the Weizmann Prize in Exact Sciences,
the IEEE Charles Babbage Award, the Harvey Prize for
Science and Technology,
the Israel Prize in Computer Science, and the EME"T Prize in Computer Science.

米凯尔·拉宾和达纳·斯科特——非确定性有限状态自动机理论的开创者编辑本段 回目录

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

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

达纳·斯科特

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

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

迈克尔·拉宾

1958年夏天，拉宾又一次来到IBM。当时，“人工智能之父”麦卡锡(J．McCarthy，1971年图灵奖获得者)正在那儿研究往巴克斯(J．Backus，1977年图灵奖获得者)发明不久的Fortran语言中加入表处理功能。他给拉宾出了一道难题：设计一种口令，即使口令被敌方窃去，也无法进入系统。拉宾经过艰苦探索，终于利用由冯·诺伊曼开发的一个单向函数解决了这个问题。所谓单向函数简单说来就是正向极易于计算而反向极难计算的函数，例如“平方取中”： y=[x2中间一半的位所组成的数]. 这样，当x为100位的数时，x2为200位的数，y则为这200位的中间100位所组成的数。由z算y是容易的，而由y求出x则非常困难，因为可能的x非常之多。正是这个问题促使拉宾进一步研究计算任务的最小计算量这一一般性问题，也就是计算的固有难度问题，从而成为最早研究计算复杂性问题的先驱之一。1959年和1960年，拉宾在耶路撒冷先后发表了有关此问题的两篇论文，即“计算速度和递归集合的分类”(Speed of computation and classification of recursivesets，3rd Convention of Sci．Sco，Israel，1959)及“函数的计算难度和递归集合的偏序“(Degree Of difficulty Of computing a function and a partialordering of recursive sets，Tech．Rep．No．1，O．N．R·，Jerusalem，1960)。论文虽然没有用“计算复杂性”这个名词而用了“计算速度”和“计算难度’’这类名词，但学术界公认这两篇论文是研究计算复杂性的最早、最权威的论文中的两篇，对1964年正式提出“计算复杂性”这一术语的哈特马尼斯(J．Hartmanis)和斯特恩斯(R．E．Sterns，这两人是1993年图灵奖获得者)以及计算复杂性理论的另一奠基人布卢姆(M．Blum，1995年图灵奖获得者)都曾产生过深刻影响。其中布卢姆正是听了拉宾的有关演说才开始研究计算复杂性并完成其博士论文的。

达纳·斯科特

拉宾的研究成果在一定程度上改变了人们的研究方向。例如，波兰数学家普里斯伯克(M．Presburger)在1930年于华沙举行的一次国际数学家会议上所发表的论文中提出了这样一个命题：只包括自然数相加运算的数学系统是完备的，也就是说这样的系统在图灵机上都是可计算的。因此这被称为普里斯伯格算术系统，不少计算机科学家试图编写出能证明这个系统中的定理的计算机程序。但拉宾指出，这是极其困难而无法实现的。对于只有100个符号的这样的系统，即使是1万亿台每秒运行1万亿次的计算机，也要运行1万亿年才能得出结果。1974年在斯德哥尔摩的IFIP大会上他作了一次学术演讲，公布了他和耶鲁大学的费歇尔(M．Fisher)的这项研究成果，宣称“这就是通向人工智能的理论障碍”。拉宾演说那天，正好是美国总统尼克松因水门事件被迫宣布辞职这一天，拉宾原以为代表们都去看尼克松演说的电视转播而不会有多少人来听讲，却不料演说一开始人们就潮水一样涌了进来，对演说的反应十分强烈，拉宾讲完以后人们在麦克风前排成长队向他提问。对于从事普里斯伯格系统研究的许多人来说，他们听了拉宾演说以后的感觉是非常难受，似乎“世界末日”到了似的。但拉宾本人则并不悲观，他认为应该放弃的只是以完全确定的方式去获得结果的企图，但完全可以利用随机性以某种方式很快获得结果，这种结果可能出错，然而出错的可能性微乎其微，也就是说可以把概率算法(probabilistic algorithm，或叫随机算法，randomize algorithm)用到这类问题中来，这是拉宾的又一个贡献。

所谓概率算法，就是带有随机操作的一类算法。这种算法在计算的某一步或某些步产生符合规定要求的随机数，然后根据产生出韵随机数决定下一步的计算。例如，在计算的某一步有两种选择：执行A或执行B。此时随机产生一个0或1。若产生的是0则执行A，若产生的是1则执行B。这相当于根据掷一枚硬币的结果(正面或反面)决定下一步的计算。

将概率的思想用到算法中始于数值计算，在计算方法中通常称作蒙特卡罗法，是在20世纪40年代中叶提出的。它的基本思想是建立概率模型，通过统计模拟或抽样得到问题的近似解。通常要求计算结果的期望值等于问题的精确解，并且计算误差的期望值随可供使用的时间增加减小。近20年来概率算法在非数值计算中得到很好的应用。例如，已经设计出关于排序和搜索、素数判定、有限域上的多项式分解和求根、字符串的模式匹配等方面的有效概率算法。概率算法同样也应用到并行计算中，得到概率并行算法。

算法

利用这种概率算法的思想拉宾在1974年斯德哥尔摩演说时就已有了萌芽，但还不够成熟。第二年休假时他去了麻省理工学院，得知了加里·米勒(Gary Miller)的研究工作。米勒证明，利用著名的黎曼假设(G．P．B．Riemann，1826—1866，德国的数学家兼物理学家)，可以用一般的确定性算法判断很大的数是否是素数。拉宾利用米勒的研究结果和数论中关于素数密度的理论，终于在1976年提出了一个判定素数的概率算法，取得了极大成功。这个算法的理论根据是：当n是合数时，在1到n—1的整数中有一半以上是n为合数的“见证人”。算法的基本做法是：随机地产生一个1与n—1之间的整数b，检查6是否是n为合数的“见证人”。若6是“见证人”，则计算结束并得出n为合数的结论；否则重复这个过程。至多进行K次，若产生的K个随机数^都不是n为合数的“见证人”，则得出n为素数的结论。算法所需要的时间为O(1OG3n)。当计算的结果是n为合数时，结果肯定是正确的。但是，“n为素数”的结果有可能是错误的。此时n为合数的概率，即得出错误结果的概率不超过1／2k。当k足够大时，这是一个很小的数。譬如，取K=10，错误的概率小于0.001。这已经是在实验中不大可能发生的事件了。实验表明，算法在实际使用中几乎不会给出错误的结论。

拉宾的一个同事普拉特(V．R．Pratt)用拉宾的算法编写了一个程序，在1975年冬找到了当时最大的素数2400—593以及最大的孪生素数AX 338+821和KX 338+823(A是小于300的所有素数的乘积)，创造了世界记录。拉宾的算法目前仍然是寻找素数的最快算法之一。

在获得图灵奖之前，拉宾曾于1974年获得由Rothschild基金会所颁发的数学奖，斯科特则于1972年因在数理逻辑方面的出色贡献而获得美国数学会的Leroy P．Steele奖。1980年拉宾又被授予哈维科技奖(Harvey Prize Sci．&Tech．)。

拉宾和斯科特是在1976年10月20日于休斯敦举行的ACM年会上被授予图灵奖的。两人分别发表了图灵奖演说，拉宾的演说题为“计算复杂性”(Complexity of Computations)，斯科特的演说题为“逻辑与程序设计语言”(10Sic and Programming Language)，它们刊载于Communications of ACM，1977年9月，625—641页，也可见《前20年的ACM图灵奖演说集》(ACM Turing Award Lectures——The First 20Years：1966—1985，ACM Pr.)，47—62页及319—338页。

拉宾目前既是美国哈佛大学教授，又是耶路撒冷希伯莱大学教授，两地奔波，而他的家则留在以色列。他的电子信箱为：rabin@deas.Harvard.edu

更多背景知识：1976年图灵奖获得者Michael Rabin编辑本段 回目录

Michael Oser Rabin (1931–)

迈克尔·拉宾

图灵奖获得时间：

1976年。第十一位图灵奖(1976年)获得者。

图灵奖引用(Turing Award Citation) ：

For their joint paper “Finite Automata and Their Decision Problem,” which introduced the idea of nondeterministic machines, which has proved to be an enormously valuable concept. Their (Scott & Rabin) classic paper has been a continuous source of inspiration for subsequent work in this field.

【笔者译：】

“( 授予 Michael O. Rabin图灵奖以表彰其 )( (与Dana Steward Scott合作撰写的研究论文)有限自动机与其判定性问题。在该研究论文中，提出了非确定性(自动机)机器的观点。(在计算理论科学研究中，)非确定性被证明是一个非常重要的概念。Rabin和Scott的这篇经典文章成为这个领域后续研究的基石。”

【笔者注：】

Rabin著名论文可参见：有限自动机与其判定性问题（PDF格式）

自动机理论介绍：
http://en.wikipedia.org/wiki/Automata_theory

http://en.wikipedia.org/wiki/Finite_state_machine

Simulation of an NFA by a DFA

关于DFA和计算理论的书籍：

http://books.google.com/books?q=Finite+Automata+and+Their+Decision+Problem&oi=print

http://books.google.com/books?q=DFA+theory+of+computing&oi=print

Comp.Theory FAQ:

迈克尔·拉宾

http://www.cs.uwaterloo.ca/~alopez-o/comp-faq/faq.html

Book of “Introduction to the Theory of Computation” from MIT:

http://www-math.mit.edu/~sipser/book.html

Turing Award Lecture(图灵奖演讲文章)：

Logic and Programming Languages. Commun. ACM 20(9): 634-641(1977)

Michael O. Rabin 简介:

Michael O. Rabin Wiki: http://en.wikipedia.org/wiki/Michael_O._Rabin

Michael O. Rabin在哈佛大学网站上的个人简历：

http://www.deas.harvard.edu/directory/professionalbio/index.html?id=2542

Answer.com关于Michael O. Rabin的介绍: http://www.answers.com/topic/michael-o-rabin

Michael Oser Rabin生于1931年于Breslau,德国的一个犹太人家庭。Beslau在二战后属于波兰。

Michael在1953年从Hebrew University of Jerusalem( http://www.huji.ac.il/ ) 获得其硕士学位;1956年从普林斯顿大学获得其博士学位。

除了其与Danna Scott合作的关于非确定性自动机理论并获得了图灵奖之外，Michael的学术生涯非常丰富，在1975年，Rabin发明了Miller-Rabin primality test; 1979年，发明了Rabin Crytosystem; 1981年发明了Oblivious Transfer; 1987年发明了Rabin-Karp String Search Algorithm。

目前，Rabin是哈佛大学计算机系的教授。可参见：

http://www.cs.harvard.edu/ 。另外，Rabin也是希伯来大学计算机系(http://www.cs.huji.ac.il/ ) 的教授。可参见：

http://www.cs.huji.ac.il/people/index.php?id=1&in=t

http://www.cs.huji.ac.il/images/personal_info.gif

关于Micahel的其他著名的算法，可参见：

Miller-Rabin primality test
Rabin cryptosystem
Rabin-Karp string search algorithm
Oblivious transfer
Michael O. Rabin照片:
http://images.google.com/images?q=Michael+O.+Rabin&hl=en&lr=&sa=N&tab=wi&sourceid=tipimg

（作者陈怀临）