Manuel Blum was born in Caracas, Venezuela on April 26, 1938.
He received a
B.S. in Electrical Engineering in 1959, an
M.S. in Electrical Engineering in 1961, and a
Ph.D. in Mathematics in 1964, all from the Massachusetts Institute
Blum has made many contributions to computational complexity and cryptography.
One of his important results is the speed-up theorem, which says roughly
that for any desired speed-up, there is a language L such that for any TM
accepting L, there exists another TM accepting L that uses only the
pre-specified fraction of the space used by the first.
- "The speed-up theorem", in Hopcroft and Ullman, Introduction to
Automata Theory, Languages, and Computation, Addison-Wesley, 1979,
Back to Theory of Computing Hall of Fame Main Page
Back to CS 462 home page