Michael Oser Rabin | |
---|---|
Born |
Breslau, Germany |
September 1, 1931
Nationality | Israeli |
Fields | Computer Science |
Institutions |
Harvard University Hebrew University Columbia University |
Alma mater |
Hebrew University (M.S.) Princeton University (Ph.D.) |
Thesis | Recursive Unsolvability of Group Theoretic Problems (1957) |
Doctoral advisor | Alonzo Church |
Doctoral students |
Moshé Machover Saharon Shelah Dov Gabbay Giuseppe Persiano |
Known for |
Miller-Rabin primality test Rabin cryptosystem Oblivious transfer Rabin-Karp string search algorithm Nondeterministic finite automata Randomized algorithms |
Notable awards |
Turing Award (1976) Paris Kanellakis Award (2003) Israel Prize Emet Prize Harvey Prize Dan David Prize Dijkstra Prize |
Michael Oser Rabin (Hebrew: מִיכָאֵל עוזר רַבִּין, born September 1, 1931), is an Israeli computer scientist and a recipient of the Turing Award.
Rabin was born in 1931 in Breslau, Germany (today Wrocław, in Poland), the son of a rabbi. In 1935, he emigrated with his family to Mandate 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 a significant practicing mathematician, Elisha Netanyahu, who was then a high school teacher.
After high school, he 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.
He received an M.Sc. from Hebrew University of Jerusalem in 1953 and a Ph.D. from Princeton University in 1956.
In the late 1950s, he 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.