#
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

- "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 462 home page

*cs462@bacon.math*

September 10 1997