ceived because Shannon was dealing
with the information content of messages. If you perform a lengthy calculation on a small input then the information content in the Shannon sense
of the outcome is still small. You can
take a 100-bit number and raise it to
the power 100, so you get a 10,000-bit
number. But the information content
of those 10,000 bits is no larger than
that of the original 100 bits.
John McCarthy posed to me a puzzle about spies, guards, and password.
Spies must present, upon returning
from enemy territory, some kind of
secret password to avoid being shot
by their own border guards. But the
guards cannot be trusted to keep a secret. So, if you give them the password,
the enemy may learn the password and
safely send over his own spies. Here is
a solution. You randomly create, say, a
100-digit number x and square it, and
give the guards the middle 100 digits
of x2. John von Neumann had suggested the middle square function for
generating pseudo-random numbers.
You give the number x to the spy. Upon
being challenged, the spy presents x.
The guard computes x2 and compares
the middle square to the value he has.
Every password x is used only once.
The whole point is that presumably it
is easy to calculate the middle square,
but it is difficult, given the middle
square, to find one of the numbers
having that value as a middle square.
So even if the guards divulge the middle square, nobody else can figure out
the number the spy knows.
But how do you even define that difficulty of computing? And even more
so, how do you prove it? I then set
myself to study that problem. I wrote
an article called “Degree of Difficulty
of Computing a Function and Hierarchy of Recursive Sets.” In that article,
I wasn’t able to solve the problem of
showing that the von Neumann function is difficult to invert. This is really
a special case of the P = NP problem.
It hasn’t been settled to this day. But
I was able to show that for every computable function there exists another
computable function that is more
difficult to compute than the first
one, regardless of the algorithm or
programming language one chooses.
It’s similar to the minimum energy
required for performing a physical
the next significant
my work on
task. If this phone is on the floor and
I have to raise it, there is a minimum
amount of work. I can do it by pulling
it up, by putting a small amount of explosive, blowing it up here, but there
is a certain inherent amount of work.
This is what I was studying for computations.
I think this paper, no less than
the Rabin/Scott paper, was a reason
for my Turing Award. The ACM announcement of the Turing Award for
Dana and for me mentioned the work
on finite automata and other work we
did and also suggested that I was the
first person to study what is now called
complexity of computations.
A new Departure
I went back to Jerusalem. I divided my
research between working on logic,
mainly model theory, and working on
the foundations of what is now computer science. I was an associate professor and the head of the Institute
of Mathematics at 29 years old and
a full professor by 33, but that was
completely on the merit of my work in
logic and in algebra. There was absolutely no appreciation of the work on
the issues of computing. Mathematicians did not recognize the emerging
In 1960, I was invited by E.F. Moore
to work at Bell Labs, where I introduced the construct of probabilistic
automata. These are automata that
employ coin tosses in order to decide which state transitions to take. I
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 if you go over to probabilistic
Shasha: And with some kind of error bound?
Rabin: Yes, yes, that’s right. In
other words, you get the answer, but
depending upon how many times you
run the probabilistic automaton, you
have a very small probability of error.
That paper eventually got published
in 1963 in Information and Control.
In 1975, I finished my tenure as
Rector (academic head) of the Hebrew
University of Jerusalem and came to
MIT as a visiting professor. Gary Miller was there and had his polynomial
time test for primality based on the
extended Riemann hypothesis. [Given
an integer n, a test for primality determines whether n is prime.] That test
was deterministic, but it depended
on an unproven assumption. With the
idea of using probability and allowing
the possibility of error, I took his test
and made it into what’s now called a
randomized algorithm, which today
is the most efficient test for primality.
I published first, but found out that
Robert Solovay and Volker Strassen
were somewhat ahead with a different
test. My test is about eight times faster
than theirs and is what is now universally being used. In the paper I also
introduced the distinction between
what are now called Monte-Carlo and
In early 1976 I was invited by Joe
Traub for a meeting at CMU and gave a
talk presenting the primality test. After
I gave that lecture, people were standing around me, and saying, “This is really very beautiful, but the new idea of
doing something with a probability of
error, however exponentially small, is
very specialized. This business of wit-nesses for compostiness you have introduced is only useful for the primality test. It will never really be a widely
used method.” Only Joe Traub said,
“No, no, this is revolutionary, and it’s
going to become very important.”
from trick to
From then on, I set myself the goal of
finding more and more applications
of randomization in mathematics and
computer science. For example, in
1977 in my MIT class, I presented an
algorithm for efficiently expressing
an integer as the sum of four squares.
Lagrange had proved in 1770 that ev-