GoKawiilIsraeli mathematician and computer scientist (1931–2026)
Michael Oser Rabin (Hebrew: מִיכָאֵל עוזר רַבִּין; September 1, 1931 – April 14, 2026) was a 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.[1]
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.[1] 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.[2]
Career
Rabin became Associate Professor of Mathematics at the University of California, Berkeley (1961–62), and MIT (1962–63). Before moving to Harvard University as Gordon McKay Professor of Computer Science in 1981, he was a professor at the Hebrew University.[3]
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".[4] Soon, using nondeterministic automata, they were able to re-prove Kleene's result that finite state machines exactly accept regular languages.[1]
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".[1][5]
... continue reading