Manuel Blum

Blum introduced axiomatic complexity theory in 1967, defining 'Blum complexity measures' as abstract axioms that any reasonable measure of computational cost must satisfy. He proved the Blum speedup theorem, which shows that for some computational problems, no single algorithm is optimal because any algorithm can always be improved.

Blum and his students at Carnegie Mellon, including Luis von Ahn, pioneered CAPTCHAs (Completely Automated Public Turing tests to tell Computers and Humans Apart) in the early 2000s. The most well-known variant, reCAPTCHA, was later acquired by Google and used to help digitize books by having humans transcribe text that OCR could not read.

Blum received the 1995 Turing Award for his contributions to the foundations of computational complexity theory and its application to cryptography and program checking. His work on self-correcting programs and program result verification showed how to check computation results even when the underlying algorithms or hardware might be unreliable.

Developed by Blum with Lenore Blum and Michael Shub in 1986, the Blum-Blum-Shub generator produces pseudorandom numbers by repeatedly squaring modulo a Blum integer (a product of two large primes). It is one of the few pseudorandom generators with a formal proof that predicting its output is as hard as factoring the modulus, making it valuable in cryptography.