迈克尔·拉宾1931—2026

生平

拉宾出生于德国布雷斯劳（二战后成为波兰弗罗茨瓦夫），父亲是一个拉比，4岁迁居至巴勒斯坦托管地。

1953年，他获得希伯来大学的理学硕士，1956年获普林斯顿大学博士学位。

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

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

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

Michael Oser Rabin (Hebrew: מִיכָאֵל עוזר רַבִּין; September 1, 1931 – April 14, 2026) was an Israeli-American computer scientist who was co-recipient, with Dana Scott, of the 1976 ACM Turing Award for their work on computational complexity.

Life and career

Early life and education

Rabin was born in 1931 in Breslau, Lower Silesia, Prussia, Germany (today Wrocław, in Poland), the son of a rabbi. In 1935, he emigrated with his family to Mandatory Palestine. As a young boy, he was very interested in mathematics and his father sent him to the best high school in Haifa, where he studied under mathematician Elisha Netanyahu, who was then a high school teacher.

He graduated from the Hebrew Reali School in Haifa in 1948, and was drafted into the army during the 1948 Arab–Israeli War. The mathematician Abraham Fraenkel, who was a professor of mathematics in Jerusalem, intervened with the army command, and Rabin was discharged to study at the university in 1949. Afterwards, he received an M.Sc from Hebrew University of Jerusalem. He began graduate studies at the University of Pennsylvania before receiving a Ph.D. from Princeton University in 1956.

Career

In the late 1950s, Rabin was invited for a summer to do research for IBM at the Lamb Estate in Westchester County, New York, with other promising mathematicians and scientists. It was there that he and Dana Scott wrote the paper "Finite Automata and Their Decision Problems". Soon, using nondeterministic automata, they were able to re-prove Kleene's result that finite state machines exactly accept regular languages.

As to the origins of what was to become computational complexity theory, the next summer Rabin returned to the Lamb Estate. John McCarthy posed a puzzle to him about spies, guards, and passwords, which Rabin studied and soon after he wrote an article, "Degree of Difficulty of Computing a Function and Hierarchy of Recursive Sets".

Nondeterministic machines have become a key concept in computational complexity theory, particularly with the description of the complexity classes P and NP.

He then returned to Jerusalem, researching logic, and working on the foundations of what would later be known as computer science. He was an associate professor and the head of the Institute of Mathematics at the Hebrew University at 29 years old, and a full professor by 33. Rabin recalls, "There was absolutely no appreciation of the work on the issues of computing. Mathematicians did not recognize the emerging new field".

In 1960, Rabin was invited by Edward F. Moore to work at Bell Labs, where Rabin introduced probabilistic automata that employ coin tosses to decide which state transitions to take. He showed examples of regular languages that required a very large number of states, but for which you get an exponential reduction of the number of states with probabilistic automata.

Rabin was a Visiting Associate Professor of Mathematics at the University of California, Berkeley in the 1961–62 school year and at MIT for the 1962-1963 school year. Before moving to Harvard University as Gordon McKay Professor of Computer Science in 1981, he was a professor at the Hebrew University.

In 1966 (published in conference proceedings in 1967), Rabin introduced the notion of polynomial time (introduced independently and very shortly before by Cobham and Edmonds).

In 1969, Rabin introduced infinite-tree automata and proved that the monadic second-order theory of n successors (S2S when n = 2) is decidable.

Awards and honours

Rabin was a foreign member of the United States National Academy of Sciences, a member of the American Philosophical Society, a member of the American Academy of Arts and Sciences, a member of the

French Academy of Sciences, and a foreign member of the Royal Society.

In 1976, the Turing Award was awarded jointly to Rabin and Dana Scott for a paper written in 1959, the citation for which states that the award was granted:

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

In 1995, Rabin was awarded the Israel Prize, in computer sciences. In 2010, Rabin was awarded the Tel Aviv University Dan David Prize ("Future" category), jointly with Leonard Kleinrock and Gordon E. Moore, for Computers and Telecommunications. Rabin was awarded an Honorary Doctor of Science from Harvard University in 2017.