Manuel Blum

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 of Technology.

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.

Sources

  1. "The speed-up theorem", in Hopcroft and Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979, pp. 308-310.
Back to Theory of Computing Hall of Fame Main Page
Back to CS 360 home page