1976 达纳·斯科特

shiyi18

Michael O. Rabin
BIRTH:
September 1, 1931 Breslau, Germany (now Wroclaw, Poland)

EDUCATION:
M.Sc., (Mathematics, Hebrew University, 1953); Ph.D., Mathematics, Princeton University, 1957.

EXPERIENCE:
Professor, Harvard (Gordon McKay Professor of Computer Science,1981-1983; Thomas J. Watson Sr. Professor of Computer Science 1983); Professor, Hebrew University of Jerusalem (Albert Einstein Chair,1980-1999; Pro-Rector, 1976-1980); Rector (Academic Head) 1972-1975; Chairman, Computer Science Department 1970-1971; Chairman, Institute of Mathematics 1964-1966; Senior Lecturer, Associate Professor and Professor 1958-1965); Institute for Advanced Study, Princeton (1958 Member; H. B. Fine Instructor1956-1958). He has also held many different visiting appointments at major universities in Europe and the United States.

HONORS AND AWARDS:
C. Weizmann Prize for Exact Sciences (1960); Best Teacher Award, Courant Institute of Mathematics (1970); Rothschild Prize in Mathematics (1974); Member American Academy of Arts and Sciences (1975); ACM Turing Award (1976); Harvey Prize in Science and Technology (1980); Israel Academy of Sciences and Humanities (1982); Foreign Associate US National Academy of Science (1984); Foreign Member American Philosophical Society (1988); President, Division for Logic, Methodology, and Philosophy of Science, IUHPS (1990-2003); Israel Prize in Exact Sciences/Computer Science (1995); Associé Étranger, French Academy of Sciences (1995); Honorary Doctorate, University of Bordeaux I (1996); Honorary Doctorate, Haifa University (1996); Honorary Doctorate, New York University (1998); Honorary Doctorate, Israel Open University Honorary Fellow (1999); IEEE Charles Babbage Award in Computer Science (2000); Honorary Doctorate, Ben-Gurion University (2000); EMET Prize in Exact Sciences/Computer Science (2004); ACM Kanellakis Theory and Pratice Award (2004); ASL Godel Award Lecture (2004); Member European Academy of Science (2007); Foreign Member Royal Society (2007); Honorary Doctorate, Wroclaw University (2007); IACR Fellow (2009); Dijkstra Prize (2015); Tel Aviv University Dan David Prize (“Future” category) jointly with Leonard Kleinrock and Gordon E. Moore, for Computers and Telecommunications.

MICHAEL O. RABIN DL Author Profile link
United States – 1976
CITATION
Along with Dana S. Scott, 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.

SHORT ANNOTATED
BIBLIOGRAPHY
ACM TURING AWARD
LECTURE
RESEARCH
SUBJECTS
VIDEO INTERVIEW
ORAL HISTORY INTERVIEW
Michael Rabin was born in 1931 in Breslau, Germany, now Wroclaw, Poland. His father, a rabbi, moved the family to Palestine in 1935. Michael was given a very good primary education and attended the best high school in Haifa.

Michael related the following story to explain how he became interested in mathematics at about the age of 10 or 11. In the hallway of his school he encountered a few older students attempting to find a proof for an elementary problem in geometry. To his delight, he was able to solve it, and he enjoyed the experience of starting with just a few known facts about a geometrical figure and deducing others that are not obvious. The idea that with thought alone one can prove geometric statements inspired him to study mathematics.

In high school he was taught mathematics by Elisha Netanyahu, the uncle of the later Israeli Prime Minister. Netanyahu was an important mathematician in his own right, and later became a professor at the Technion in Haifa and Dean of the Faculty of Science. While a high school teacher, Netanyahu organized a weekly seminar to teach topics in advanced mathematics to a select group of students. Rabin participated, and quickly learned much more than would be the norm for a student of his age.

Rabin finished high school at the age of 16. Like most of his classmates, he was then drafted into the army to fight for the independence of the then-new state of Israel. He filled the periods of inactivity by reading mathematics textbooks. One by Professor Abraham Fraenkel in Jerusalem was on set theory, and Rabin wrote to him. Fraenkel, impressed by the depth of the correspondence, met with Rabin and later was instrumental in having him mustered out of the military to attend the University of Jerusalem. He was admitted directly into a Master’s degree program to study algebra, and graduated in 1953. His thesis solved a significant open problem that had been proposed by the German mathematician Emmy Noether.

Rabin describes his time at Hebrew University and his undergraduate thesis work.       
On the strength of the thesis he was admitted to a PhD program at Princeton, where he studied under Alonzo Church and graduated in 1957. After Rabin finished his PhD he was invited by IBM to attend a summer research workshop for a select group of young scientists. It was there that he and Dana Scott collaborated on the famous paper “Finite Automata and Their Decision Problem” [1] that led to their joint Turing Award in 1976.

Rabin describes his graduate studies at the University of Pennsylvania and (under Alonzo Church) at Princeton.       
Automata theory had really begun with the 1943 study of artificial neural networks by Walter Pitts and Warren McCulloch. Others continued this biologically-inspired work. Rabin and Scott moved away from neural networks, and instead used a computational model known as a finite state machine. These theoretical machines, like the Turing machine, move from one state to another depending on the input and the defined transition rules. Finite state machines had been investigated before, but Rabin and Scott considered different kinds. One was a nondeterministic machine that did not just have one possible transition out of each state, but had several. Essentially the machine could, upon accepting an input symbol, replicate itself, and then each machine would proceed with the computation along one of the possible transitions. As noted in the citation for the Turing Award, this concept of a nondeterministic machine has proven to be extremely valuable in the theoretical investigation of many problems, and continues to be an inspiration for new work.

Rabin recounts the work with Dana Scott that led to their 1959 paper “Finite Automata and their Decision Problems”.       
The next summer Rabin was again invited to the IBM research workshop.  He met another future Turing Award recipient, John McCarthy, who explained a puzzle to him about spies and guards. The spies have passwords that allow them to pass from enemy territory to their own. The guards cannot be trusted to keep the passwords secret, so some method had to be found to verify that even if the enemy gains knowledge of the password, the spies can safely return but the enemy infiltrators are kept out. One solution came from the middle-square method, which had been proposed by mathematician John von Neumann as a way of generating random numbers. Each spy is given a 100-digit number x, and the guards are given another 100-digit number obtained by taking the middle digits from x2. When returning, the spy gives the guard x. The guard then computes x2 and compares the middle digits to the number he possesses as a pass code. Even if the guard passes his number to an enemy, it is very difficult for the enemy to determine what initial number resulted in those 100 middle digits of x2.

Rabin retells the story about guards and spies that led him to work on degrees of computational difficulty.       
Rabin began thinking in general about functions that are difficult to invert —in this case computing the original number x knowing only the middle digits of x2. His study resulted in the groundbreaking paper [2] “Degree of Difficulty of Computing a Function and a Partial Ordering of Recursive Sets”,  which was the starting point for his later advances in the theoretical study of computational complexity particularly in relation to cryptography.

Rabin had returned to the University of Jerusalem, first as a senior lecturer, then as Associate Professor, and then Professor. He kept up his prodigious research output while also becoming chairman of their Institute of Mathematics, chairman of the Department of Computer Science, and Rector (academic head) of the entire University.

In 1975, having finished his term at Rector, he went to MIT as a Visiting Professor and worked on primality testing with Gary Miller. This involves determining if a very large number is prime—whether the number has no divisors other than itself and 1. Miller had earlier developed a primality test that was based on the unproven Riemann hypothesis. That bothered Rabin, because if the Riemann hypothesis was eventually shown to be false it would bring into question any methods based on it. Michael had earlier worked on probabilistic automata, theoretical machines for which a random number is used to determine which transition to take from each state. While not deterministic in the sense that it always provides a provable result, if run a number of times the chance of it being incorrect can be made vanishingly small. Rabin used this concept to develop a primality testing algorithm [3] called the Miller-Rabin test. It was later shown to be deterministic: it is guaranteed to work if a certain number of tests were done.

Rabin explains the concept of probabilistic automata and his work with Gary Miller to apply it to prime testing.       
Adding randomness to algorithms was to be a theme for much of Rabin’s later work on many different problems. One of his favorites, the four-square problem that had first been discussed by Joseph-Louis Lagrange in 1770, was how to express an integer as the sum of four squares: for any integer y find four not necessarily unique, integers a, b, c, d such that y = a2 + b2 + c2 + d2. Lagrange had shown that it is always possible, but nobody knew an efficient algorithm to find a, b, c and d. In speaking to a class of students at MIT in 1977 Rabin proposed a randomized algorithm, which he and Jeff Shallit later published as part of a larger study of randomized algorithms [4].

Rabin’s later work concerns cryptographic problems for preventing piracy on the internet. Recently he has been examining how to ensure the privacy and secrecy of online auctions. In auctions like those conducted by Google for advertising slots, the participants want their identity and bidding strategy to remain anonymous, but want to be assured that the results of the auction are fair. Rabin has worked as a consultant to create a zero-knowledge proof that gives such assurances.



Michael O. Rabin
出生时。
1931年9月1日，德国布雷斯劳（现波兰弗罗茨瓦夫）。

学历：理科硕士（希伯来大学数学，1953年）；数学博士（希伯来大学）。
理学硕士，（数学，希伯来大学，1953年）；数学博士，普林斯顿大学，1957年。

经历：哈佛大学教授（戈登-麦肯锡教授）。
哈佛大学教授（Gordon McKay计算机科学教授，1981-1983；Thomas J. Watson Sr. 计算机科学教授，1983）。1983年）；耶路撒冷希伯来大学教授（阿尔伯特-爱因斯坦讲座，1980-1999年；副校长，1976-1980年）；校长（学术负责人）1972-1975年；计算机科学系主任1970-1971年；数学研究所主席1964-1966年；高级讲师、副教授和教授1958-1965年）；普林斯顿高等研究所（1958年成员；H. B. Fine讲师1956-1958）。他还在欧洲和美国的主要大学担任过许多不同的访问职务。

荣誉和奖项。
C. 魏茨曼精确科学奖（1960年）；库兰特数学研究所最佳教师奖（1970年）；罗斯柴尔德数学奖（1974年）；美国艺术与科学学院成员（1975年）；ACM图灵奖（1976年）；哈维科技奖（1980年）；以色列科学与人文学院（1982年）。美国国家科学院外籍院士（1984年）；美国哲学学会外籍会员（1988年）；IUHPS逻辑学、方法学和科学哲学分部主席（1990-2003年）；以色列精确科学/计算机科学奖（1995年）；法国科学院Associé Étranger（1995年）；波尔多第一大学荣誉博士（1996年）。海法大学名誉博士（1996年）；纽约大学名誉博士（1998年）；以色列开放大学名誉博士，名誉研究员（1999年）；IEEE查尔斯-巴贝奇计算机科学奖（2000年）；本古里安大学名誉博士（2000年）；EMET精确科学/计算机科学奖（2004年）。ACM卡内拉基斯理论与实践奖（2004年）；ASL戈德尔奖讲座（2004年）；欧洲科学院院士（2007年）；英国皇家学会外国会员（2007年）；弗罗茨瓦夫大学荣誉博士（2007年）；IACR研究员（2009年）；Dijkstra奖（2015年）；特拉维夫大学丹-大卫奖（"未来 "类），与Leonard Kleinrock和Gordon E. Moore联合颁发。摩尔共同设立的计算机和电信奖。

MICHAEL O. RABIN DL作者简介链接
美国 - 1976年
奖状
与Dana S. Scott共同发表论文 "有限自动机及其决策问题"，提出了非决定性机器的概念，该概念已被证明是一个非常有价值的概念。他们（斯科特和拉宾）的经典论文一直是该领域后续工作的灵感来源。

简短注释的
书目
亚马逊图灵奖
讲座
研究
主题
视频采访
口述历史采访
迈克尔-拉宾1931年出生在德国的布雷斯劳，现在是波兰的弗罗茨瓦夫。他的父亲是一名拉比，1935年举家迁往巴勒斯坦。迈克尔接受了非常好的小学教育，并在海法最好的中学上学。

迈克尔讲述了以下故事来解释他是如何在10或11岁时对数学感兴趣的。在学校的走廊里，他遇到了几个高年级的学生，他们试图为几何学中的一个初级问题找到一个证明。令他高兴的是，他能够解决这个问题，而且他很享受这种从一个几何图形的几个已知事实开始，推导出其他不明显的事实的经验。仅仅通过思考就能证明几何语句的想法激发了他学习数学的兴趣。

在高中时，他被后来的以色列总理的叔叔埃利沙-内塔尼亚胡教导数学。内塔尼亚胡本身就是一位重要的数学家，后来成为海法技术学院的教授和理学院院长。在担任高中教师时，内塔尼亚胡组织了一个每周一次的研讨会，向一群经过挑选的学生讲授高等数学的课题。拉宾参加了这一活动，并很快学到了比他这个年龄段的学生所能学到的更多。

拉宾在16岁时完成了高中学业。像他的大多数同学一样，他随后被征召入伍，为当时新的以色列国的独立而战。他通过阅读数学教科书来填补这段闲置的时间。其中一本由耶路撒冷的亚伯拉罕-弗莱恩克尔教授编写的集合理论，拉宾写信给他。弗拉恩克尔对这些信件的深度印象深刻，会见了拉宾，并在后来帮助他从军队中退役，进入耶路撒冷大学学习。他被直接录取到一个研究代数的硕士学位课程，并于1953年毕业。他的论文解决了德国数学家埃米-诺特提出的一个重要的公开问题。

拉宾描述了他在希伯来大学的时光和他的本科论文工作。       
凭借论文，他被普林斯顿大学的博士课程录取，在那里他在阿隆佐-丘奇的指导下学习，并于1957年毕业。拉宾完成博士学业后，他被IBM邀请参加一个为精选的年轻科学家团体举办的夏季研究讲习班。正是在那里，他和达纳-斯科特合作完成了著名的论文《有限自动机及其决策问题》[1]，并在1976年获得了他们共同的图灵奖。

拉宾描述了他在宾夕法尼亚大学和（在Alonzo Church的带领下）在普林斯顿的研究生学习。       
自动机理论真正开始于1943年Walter Pitts和Warren McCulloch对人工神经网络的研究。其他人继续这项受生物启发的工作。拉宾和斯科特远离了神经网络，转而使用一种被称为有限状态机的计算模型。这些理论上的机器，像图灵机一样，根据输入和定义的过渡规则，从一个状态移动到另一个状态。有限状态机以前也被研究过，但拉宾和斯科特考虑了不同的类型。其中一种是非确定性机器，它不只是在每个状态下有一个可能的过渡，而是有几个。从本质上讲，机器在接受一个输入符号时，可以复制自己，然后每个机器将沿着一个可能的过渡进行计算。正如图灵奖颁奖词中所指出的，这种非决定性机器的概念在许多问题的理论研究中被证明是非常有价值的，并继续成为新工作的灵感来源。

拉宾讲述了与达纳-斯科特的工作，他们在1959年发表了论文《有限自动机及其决策问题》。       
第二年夏天，拉宾再次被邀请参加IBM的研究研讨会。 他遇到了另一位未来的图灵奖获得者约翰-麦卡锡，后者向他解释了一个关于间谍和警卫的难题。间谍有密码，可以让他们从敌人的领土上通过到自己的领土上。不能相信卫兵会对密码保密，所以必须找到一些方法来验证，即使敌人知道了密码，间谍也能安全返回，但敌人的渗透者却被挡在外面。一个解决方案来自于中间平方法，它是由数学家约翰-冯-诺伊曼提出的一种生成随机数的方法。每个间谍得到一个100位数的数字x，警卫得到另一个100位数的数字，从x2中抽取中间的数字得到。当返回时，间谍将x交给警卫，然后警卫计算x2，并将中间的数字与他拥有的数字进行比较，作为通行密码。即使警卫把他的号码传给了敌人，敌人也很难确定是什么初始号码导致了x2的那100个中间数字。

拉宾复述了关于卫兵和间谍的故事，这使他开始研究计算难度的程度。       
拉宾开始一般性地思考那些难以反转的函数--在这种情况下，在只知道x2的中间数字的情况下计算原数x。他的研究导致了开创性的论文[2]"计算一个函数的困难程度和递归集的部分排序"，这是他后来在计算复杂性的理论研究，特别是与密码学有关的理论研究中取得进展的出发点。

拉宾回到了耶路撒冷大学，先是担任高级讲师，然后是副教授，最后是教授。他保持着惊人的研究产出，同时也成为数学研究所的主席，计算机科学系的主席，以及整个大学的校长（学术负责人）。

1975年，在结束校长任期后，他作为客座教授前往麻省理工学院，与加里-米勒一起研究原始性测试。这涉及到确定一个非常大的数字是否是基数--该数字是否除了它本身和1之外没有除数。米勒早些时候开发了一个基数测试，它是基于未经证实的黎曼假设。这让拉宾感到不安，因为如果黎曼假说最终被证明是错误的，这将使任何基于它的方法受到质疑。迈克尔早些时候曾研究过概率自动机，即用随机数来决定从每个状态下采取何种过渡的理论机器。虽然从它总是提供一个可证明的结果的意义上来说不是决定性的，但如果运行若干次，它不正确的机会可以变得很小。拉宾利用这个概念开发了一种称为米勒-拉宾测试的初等性测试算法[3]。它后来被证明是确定性的：如果做了一定数量的测试，它就能保证工作。

拉宾解释了概率自动机的概念以及他与加里-米勒合作将其应用于素数测试的工作。       
将随机性添加到算法中是拉宾后来在许多不同问题上的工作的主题。他最喜欢的一个问题是约瑟夫-路易-拉格朗日在1770年首次讨论的四方问题，即如何将一个整数表示为四个平方的总和：对于任何整数y，找到四个不一定唯一的整数a、b、c、d，使得y=a2+b2+c2+d2。拉格朗日已经证明这总是可能的，但没有人知道找到a、b、c和d的有效算法。1977年，拉宾在对麻省理工学院的一班学生演讲时提出了一个随机算法，他和Jeff Shallit后来发表了这个算法，作为随机算法的更大研究的一部分[4]。

拉宾后来的工作涉及防止互联网盗版的密码学问题。最近他一直在研究如何确保在线拍卖的隐私和保密性。在像谷歌进行的广告时段的拍卖中，参与者希望他们的身份和出价策略保持匿名，但又希望保证拍卖结果是公平的。拉宾曾作为顾问创建了一个零知识证明，提供这种保证。