Prof. Michael Rabin recently received yet another prestigious piece of paper to add to the impressive collection already hanging on the walls of his Jerusalem study. This one came from Harvard.
- Einstein’s theory of relatives: A personal look at the man behind the brain
- The Jewish codebreaker who helped Alan Turing crack the Nazis' Enigma machine
- 1913: An eccentric mathematician who spent a lifetime crashing with friends is born
This year’s recipients of honorary doctorates included Facebook founder and Harvard dropout Mark Zuckerberg, and Rabin, a legendary professor at Harvard and the Hebrew University of Jerusalem.
Rabin has now received every major prize in computer science – including the Turing Award and the Israel Prize – and is one of the field’s pioneers and forming fathers. He will celebrate his 86th birthday in September.
At the awards ceremony in Massachusetts in May, Harvard President Drew Faust called Rabin a “prime aficionado of algorithms and automata” and the “high-capacity hard drive of Harvard computer science, whose impact is as incalculable as his cryptosystems are uncrackable.”
Actually, Rabin’s wall doesn’t actually have room for his latest honorary doctorate in science (which is written in Latin), so for now it rests on one of the packed shelves in his study. In front of it is his first major prize – the Weizmann Prize for Exact Sciences, which he received back in 1960 when he was only 29.
“Dr. Rabin is a scientist who has at his young age won international recognition in the field of mathematical logic. His main research is dedicated to decision problems in algebra and theoretical problems related to modern computers,” states the award, which was signed, among others, by Prof. Ernst David Bergmann, the father of Israel’s nuclear program.
Foreseeing the future
Rabin tells Haaretz that at the beginning of his career, he was unclear quite how far the computer revolution would go. “I understood it had a future. I knew there would be a revolution, but its dimensions, as we see them and watch them today – and this is not the end – I didn’t see that,” he says. “As Churchill said about the [battle for] North Africa, “Now this is not the end. It is not even the beginning of the end. But it is, perhaps, the end of the beginning.’ We are there now.”
Rabin was born in 1931, to a Jewish family from Breslau in Germany (today Wroclaw, Poland). His father, Dr. Israel Abraham Rabin, was rector of the Breslau Jewish Theological Seminary, while his mother, Dr. Esther Rabin, was a writer of children’s literature. His older sister, Prof. Miriam Ben-Peretz, was awarded the Israel Prize in education. His half-brother (from his father’s first marriage) was well-known linguist Chaim Menachem Rabin.
How did three siblings from the same family become professors, with two of you receiving the Israel Prize? Is it genetics? Education? A combination of the two?
“A combination. Genetics, culture and also family culture – and, of course, national culture too. If we had been born in another place, it would not have happened.”
In 1935, the family fled the Nazis and came to Israel. They settled in Haifa. Alongside the Arab Revolt and the rioting there from 1936 through 1939, and then World War II, Rabin’s genius for math also came to light.
How did it start?
“My talent for mathematics was discovered at a young age. My father hired private tutors for me for math and physics,” he says. Even after all these years, he still describes the moment he discovered math with a glint in his eyes.
“At first I wanted to be a microbiologist because of the book ‘Microbe Hunters.’” But then, one day in seventh grade, after he was thrown out of class, he ran into two older students in the hallway who were trying to solve a geometry problem.
Rabin took one look and immediately understood the solution. “I found so much beauty and power,” he says with a smile. “The realization that pure thought could prove claims about the real world enchanted me.”
Initially, his desire to study at the Hebrew Reali School in Haifa – the best school for the exact sciences – ran up against his father’s wishes for him to study in a religious school. For two years they fought, until his father eventually relented and allowed him to attend the Reali school. His father’s fears, by the way, were well founded: “Studying physics cut me off from religion,” says Rabin.
One of Rabin’s teachers was the mathematician Elisha Netanyahu – uncle of Prime Minister Benjamin Netanyahu, and the brother of Netanyahu’s father, historian Benzion. Elisha Netanyahu helped develop Rabin’s genius for math in high school and provided him with study materials from the university. Chaim Rabin, Michael’s stepbrother, also sent him books to study from Oxford.
In 1950, after serving in the artillery during the War of Independence, Rabin began studying math at the Hebrew University. He was interested mostly in algebra and logic. At the same time he read original articles from the 1930s by such esteemed mathematicians-logicians as Kurt Gödel, Alan Turing, Alonzo Church and Emil Leon Post, which introduced the concept of computability to mathematics.
Their work was the scientific basis for the development of electronic computers in the 1940s and ’50s. In particular, Turing’s articles on computational theory and the mathematical machines later known as “Turing machines” captured his imagination.
“At the time, stories about the large computers built at Princeton, Harvard and other places began to appear in the newspapers. Compared to today, computers were primitive then,” says Rabin.
So you decided to study at Princeton?
“It was clear to me that, along with this new technology of computers and large-scale computation, there was a need for a theory that would serve as the scientific basis for this technology. And this was something that attracted me to computer science. I started working on basic problems of what is today called computer science.”
The general public is not meant to understand the subject of his doctoral thesis, “Recursive Unsolvability of Group Theoretic Problems,” which he wrote at Princeton, and he received his PhD in 1956.
In 1957, IBM invited Rabin and a number of other prominent young scientists to do research at its labs for the summer, and he returned the following year too. Along with his friend Dana Scott, the work they did there led to the classic paper “Finite Automata and Their Decision Problems,” which became one of the most cited works in computer science.
In the summer of 1958, Rabin became interested in computational complexity. “I asked myself the following question: If we have a certain computational problem, what is its inherent internal difficulty? What is the internal complexity for the solution of this problem? In other words, what is the minimum concerning computational means that we need to invest to solve the problem, even if we find the best algorithm.” These ideas later received the name “complexity of computations.” This is the work for which he was awarded the Turing Award in 1976, along with Scott.
In 1958, Rabin was appointed as senior lecturer at Hebrew University; in 1960 he became an associate professor and then five years later full professor. He founded the computer science department there in 1970. “It wasn’t simple. The hardest thing was to find teachers, and with great difficulty we found three teachers,” he once said. He was appointed rector of the university in 1972.
He has also been a professor at Harvard since 1982, with a special arrangement allowing him to alternate semesters between the two universities.
Not in layman’s terms
To describe Rabin’s pioneering mathematical work in layman’s terms is rather difficult, so it is easier to let the prizes he has been awarded speak for themselves – in their own words.
In 2010, when he was awarded the Dan David Prize, the judges wrote that he “started the entire research area of automata theory that became the foundation of all work on specification, design and verification of computing systems. This work is thus the cornerstone of the entire area of secure communication, which is absolutely essential in the internet age. This work has far-reaching implications on distributed computing, and will continue to shape electronic commerce, the internet and mobile computing for years to come. This work is bound to have a tremendous impact in a future in which more and more sensitive information is transmitted on the internet and stored in databases, making secrecy, privacy and protection ever more crucial to society.”
When he was awarded the prestigious EMET Prize in 2004, the prize jury wrote: “Pursuing the creation of a scientific foundation for computer technology, Rabin published two works that were to become cornerstones in computer science. Over the years, he has been involved in algorithm theory, inventing randomized algorithms and numerous other innovations in the field, including logical tools that play a central role in computer program verification theory. In recent years, he invented an encryption method that is provably unbreakable.” It also called him one of the greatest scientists in the field since Turing.
The Israel Prize committee said he had a special place at the head of Israeli computer scientists, and was one of the world’s finest ever.
In 1995, Rabin was the first person to be awarded the Israel Prize in computer sciences. Then-Prime Minister Yitzhak Rabin awarded him the prize, in one of his final public appearances before he was assassinated that November.
“He was very shy and told me, ‘Very nice, very nice,’” recalls Michael Rabin, with a smile.