The Turing Award and Israel Prize winner made fundamental contributions to automata, probabilistic algorithms, complexity, and cryptography, and helped build the academic infrastructure of computer science in Israel.
Prof. Michael Ozer Rabin, who died in Jerusalem on April 14, 2026 at the age of 94, was one of the Israeli scientists whose influence extends far beyond the confines of academia. He did more than just research computers. He was among those who helped define what computation is, what can be computed, how difficult it is to compute, and how reliable digital systems can be built even in a world of uncertainty. For this reason, it is difficult to describe the history of modern computer science without his name. The Israel National Academy of Sciences described him as one of the founders of modern computer science and a pioneer in mathematical logic, algorithms, cryptography, and computational complexity. (academy.ac.il)
Rabin was born in 1931 in Breslau, Germany, now Wrocław, Poland. His family immigrated to Israel in 1935, and he grew up in Haifa. His inclination for mathematics was evident from his childhood. He later studied at the Hebrew University, continued his studies in the United States, and received a doctorate from Princeton University under the supervision of the renowned logician Alonzo Church. This connection between logic, mathematics, and computation accompanied his entire career. He returned to Israel at an early stage, and was one of the researchers who built the field when “computer science” was not yet a clear and well-established academic field. (amturing.acm.org)
Turing Award in 1976
Rabin's big international breakthrough came with his joint paper with Dana Scott, “Finite Automata and Their Decision Problems.” For this work, the two received the 1976 Turing Award, the most prestigious award in computer science. The paper introduced the idea of nondeterministic machines, an idea that became a cornerstone in understanding computation, formal languages, complexity, and algorithms. In simple terms, Rabin and Scott showed that computation can be thought of not only as a rigid sequence of steps, but also as a system that explores several possibilities simultaneously at a conceptual level. This idea has influenced generations of researchers, and also the way fundamental questions in computer science are formulated to this day. (amturing.acm.org)
One of Rabin's most important contributions was the systematic introduction of randomness into the world of algorithms. In the everyday world, randomness sounds like a lack of control. For Rabin, it became a mathematical tool. He showed that in some cases, an algorithm that uses randomness can be faster and more efficient than a deterministic algorithm, while still providing a very reliable answer. This approach underlies the field of probabilistic algorithms, and has influenced large-scale computations, brute force testing, encryption, information retrieval, and distributed systems.
Miller-Rabin test for checking the primality of a number
A well-known example of this is the Miller-Rabin test for checking primality. The primality of large numbers is an ancient mathematical question, but in the digital age it has taken on very practical significance, partly because of its role in encryption. The test allows one to quickly check whether a large number is likely to be prime, with a very small error probability that can be further reduced. This is one of the places where a deep mathematical idea has become a tool in the world of computing and security.
Rabin was also a pioneer in cryptography. Rabin's encryption system and concepts such as Oblivious Transfer influenced the foundations of modern encryption and protocols for secure computing. These fields are now behind systems that enable information transfer, identity verification, and privacy in the digital space. Rabin's contributions were not limited to one question or one technology. They touched on the fundamental infrastructure of trust, confidentiality, and computation in a computerized world.
Rabin was also a central figure in the development of computer science in Israel. He served in senior positions at the Hebrew University, including as rector of the university from 1972 to 1975, and was among those who helped to put the field on a solid academic footing. The Weizmann Institute described him as one of the academic founders of the fields on which the Israeli high-tech industry later rested. This is a particularly important point: Israeli high-tech did not grow only from a spirit of entrepreneurship, but also from a deep scientific infrastructure, built over decades in universities. Rabin was one of the important figures in this infrastructure. (Weizmann Institute of Science)
He also served as a professor at Harvard.
Alongside his work in Israel, Rabin was also a professor at Harvard University, where he held the title Thomas J. Watson Sr. Professor of Computer Science, Emeritus. He is one of a small group of researchers who have managed to operate simultaneously in the heart of Israeli academia and in the most important centers of computer science in the United States. He has been awarded many prizes over the years, including the Turing Award, the Israel Prize in Computer Science, the Harvey Prize, the A.M.T. Prize and the Dan David Prize. (amturing.acm.org)
Rabin's death is an opportunity to remember the generation of scientists who built the computer before it became a household product, a smartphone, or the infrastructure of artificial intelligence. They dealt with questions that seemed very abstract: What is a machine? What is proof? What is efficient computation? Can a process that uses randomness be trusted? Today, these questions are at the heart of our lives. They affect information security, search engines, financial systems, artificial intelligence, and every digital service that makes decisions at breakneck speed.
Prof. Michael Rabin's legacy is therefore twofold. On the one hand, it is a scientific legacy of laws, algorithms, and mathematical models. On the other hand, it is a broader Israeli legacy: building a new academic field, nurturing generations of researchers, and proving that deep theoretical thought can become, sometimes after years, the infrastructure of an entire world.
More of the topic in Hayadan:
