1959年，拉宾和达纳·斯科特共同发表了“有限自动机与其判定性问题”（Finite Automata and Their Decision Problems）的论文，提出了非确定自动机的观点。他们也因此获得了1976年的图灵奖，并做“计算机复杂性”（Complexity of Computations）的演讲。图灵奖的引文是：
^英文为：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. ACM Turing Award Citation[永久失效連結]
^Rabin, MO. Decidability of second order theories and automata on infinite trees. Trans. AMS. 1969, 141: 1–35 [2009-01-06]. doi:10.2307/1995086. （原始内容于2020-06-12）.
^Rabin, MO. Probabilistic algorithms. Algorithms and Complexity, Proc. Symp. Pittsburgh. 1976.
^Rabin, MO. Probabilistic algorithm for testing primality. Journal of Number Theory. 1980, 12 (1): 128–138. doi:10.1016/0022-314X(80)90084-0.
^Rabin, MO. (PDF). {MIT Laboratory of Computer Science Technical Report. January 1979 [2007-03-15]. （原始内容 (PDF)存档于2006-09-21）.
^Rabin, Michael O., How to exchange secrets by oblivious transfer (Technical Report TR-81) (PDF), Aiken Computation Laboratory: Harvard University, 1981 [2009-01-06], （原始内容 (PDF)于2021-11-23）
^Karp, RM; Rabin, MO. Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development. March 1987, 31 (2): 249–260 [2007-03-15].引文使用过时参数coauthors (帮助)
外部链接
Short Description in an Information Science Hall of Fame at University of Pittsburgh （页面存档备份，存于互联网档案馆）
Oblivious transfer
Quotes from some of Professor Rabin's classes （页面存档备份，存于互联网档案馆）
Website for one of Rabin's courses （页面存档备份，存于互联网档案馆）
二月 18, 2023
迈克尔, 拉宾, 科学家, 提示, 此条目的主题不是麥可, 拉賓, 小提琴家, 迈克尔, 拉宾, michael, oser, rabin, 希伯來語, יכ, ין, 1931年9月1日, 是一名以色列计算机科学家, 1976年图灵奖得主, 迈克尔, 拉宾michael, oser, rabin出生, 1931, 1931年9月1日, 91歲, 德国魏瑪共和國布雷斯劳, 今波兰弗罗茨瓦夫, 知名于米勒, 拉宾素数检验拉宾密码系统, 英语, rabin, cryptosystem, 不经意传输拉宾, 卡普字符串搜索. 提示 此条目的主题不是麥可 拉賓 小提琴家 迈克尔 O 拉宾 Michael Oser Rabin 希伯來語 מ יכ א ל א ש ר ר ב ין 1931年9月1日 是一名以色列计算机科学家 1976年图灵奖得主 迈克尔 拉宾Michael Oser Rabin出生 1931 09 01 1931年9月1日 91歲 德国魏瑪共和國布雷斯劳 今波兰弗罗茨瓦夫 知名于米勒 拉宾素数检验拉宾密码系统 英语 Rabin cryptosystem 不经意传输拉宾 卡普字符串搜索算法非确定有限状态自动机随机化算法奖项图灵奖 1976 Paris Kanellakis Award 英语 Paris Kanellakis Award 2003 以色列奖艾迈特艺术科学与文化奖 英语 EMET Prize 哈维奖 丹 大卫奖戴克斯特拉奖 英语 Dijkstra Prize IEEE计算机协会查尔斯 巴贝奇奖 英语 International Parallel and Distributed Processing Symposium IEEE Computer Society Charles Babbage Award 科学生涯研究领域计算机科学机构哈佛大学希伯来大学哥伦比亚大学生平 编辑拉宾出生于德国布雷斯劳 二战后成为波兰弗羅茨瓦夫 父亲是一个拉比 1953年 他获得希伯来大学的理学硕士 1956年获普林斯顿大学博士学位 1959年 拉宾和达纳 斯科特共同发表了 有限自动机与其判定性问题 Finite Automata and Their Decision Problems 的论文 提出了非确定自动机的观点 他们也因此获得了1976年的图灵奖 并做 计算机复杂性 Complexity of Computations 的演讲 图灵奖的引文是 因他们的合著论文 有限自动机与其判定性问题 论文中引入了非确定自动机的概念 被证明是 计算理论科学研究中的 一个非常重要的概念 拉宾和斯科特的这篇经典论文成为了这个领域后续研究的源泉 1 非确定自动机已经成为计算复杂度理论中的一个重要概念 特别是在描述P与NP问题的复杂度类时 1969年 拉宾证明N successors的二阶逻辑是可判定的 2 证明的关键部分暗示了奇偶游戏 英语 Parity game 的确定性 1975年 拉宾发明了米勒 拉宾检验 这是一个相当快速的随机化算法 有较小的可能性错误 用于判断一个大数是否是素数 3 4 快速素数检验是目前大部分公钥密码体系的关键 1979年 拉宾发明了第一个非对称密码系统 拉宾密码系统 英语 Rabin cryptosystem 它的安全性被证明和整数因式分解的复杂度相同 5 1981年 拉宾提出了不经意传输技术 6 1987年 拉宾和理查德 卡普提出了一个著名的字符串搜索算法 拉宾 卡普算法 7 参考 编辑 英文为 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 amp Rabin classic paper has been a continuous source of inspiration for subsequent work in this field ACM Turing Award Citation 永久失效連結 Rabin MO Decidability of second order theories and automata on infinite trees Trans AMS 1969 141 1 35 2009 01 06 doi 10 2307 1995086 原始内容存档于2020 06 12 Rabin MO Probabilistic algorithms Algorithms and Complexity Proc Symp Pittsburgh 1976 Rabin MO Probabilistic algorithm for testing primality Journal of Number Theory 1980 12 1 128 138 doi 10 1016 0022 314X 80 90084 0 Rabin MO Digital signatures and public key functions as intractable as factorization PDF MIT Laboratory of Computer Science Technical Report January 1979 2007 03 15 原始内容 PDF 存档于2006 09 21 Rabin Michael O How to exchange secrets by oblivious transfer Technical Report TR 81 PDF Aiken Computation Laboratory Harvard University 1981 2009 01 06 原始内容存档 PDF 于2021 11 23 Karp RM Rabin MO Efficient randomized pattern matching algorithms IBM Journal of Research and Development March 1987 31 2 249 260 2007 03 15 引文使用过时参数coauthors 帮助 外部链接 编辑Short Description in an Information Science Hall of Fame at University of Pittsburgh 页面存档备份 存于互联网档案馆 Oblivious transfer Quotes from some of Professor Rabin s classes 页面存档备份 存于互联网档案馆 Website for one of Rabin s courses 页面存档备份 存于互联网档案馆 取自 https zh wikipedia org w index php title 迈克尔 拉宾 科学家 amp oldid 70484048, 维基百科，wiki，书籍，书籍，图书馆，
