Manuel Blum: From Complexity to CAPTCHA

Zusammenfassung

Manuel Blum’s fingerprints are on three different revolutions. In the 1960s he helped found computational complexity theory, proving — before the field had names for such things — that the difficulty of a problem can be studied independently of any particular machine. In the 1980s he turned hardness from an obstacle into a tool, with protocols like coin flipping by telephone and pseudorandom generators that helped make cryptography a science. Around 2000 he and his student Luis von Ahn weaponized the gap between human and machine perception as the CAPTCHA, the reverse Turing test billions of people have squinted at. He won the 1995 Turing Award — and, in the achievement colleagues consider his greatest, advised a string of doctoral students that includes three more Turing laureates. He has spent his ninth decade on the problem that drew him into science in the first place: a computational theory of consciousness.

The Boy Who Wanted to Understand Brains

Manuel Blum (born April 26, 1938 in Caracas, Venezuela) has told the story all his life: as a struggling young student he asked how he could become smarter, was told the brain was the thing to study, and never let go of the question. He went to MIT intending to understand minds, took degrees in electrical engineering (B.S. 1959, M.S. 1961), did early work in Marvin Minsky’s orbit — including a stint studying neural models — and wrote his 1964 mathematics Ph.D. under Minsky’s supervision. The brain question proved premature; the detour became the career. In 1968 he joined UC Berkeley’s computer science faculty, where he stayed for over three decades before moving to Carnegie Mellon in 2001.

Inventing Complexity Theory

Blum’s dissertation work, published as “A Machine-Independent Theory of the Complexity of Recursive Functions” (JACM, 1967), asked a question nobody had formalized: can we say how hard a function is to compute without committing to a specific computer? His answer — two simple axioms, now the Blum axioms, that any reasonable cost measure (time, space, ink) must satisfy — founded abstract complexity theory and yielded genuinely strange theorems. The Blum speedup theorem shows there exist problems with no best algorithm: for some functions, every program can be beaten by another that is dramatically faster on almost all inputs, forever. The axiomatic approach predates and complements the P-vs-NP framework that soon reorganized the field (see P vs. NP and Complexity Theory); his 1995 Turing Award citation credits him with laying complexity theory’s foundations — and with the two applications that followed.

Hardness as a Resource

The 1980s Berkeley school Blum led made a conceptual U-turn the citation calls out: if some problems are reliably hard, hardness can be used. His 1981 protocol for coin flipping by telephone let two people who distrust each other — his example was a divorcing couple dividing property — flip a fair coin over a phone line, with cheating as hard as factoring. It was a founding act of modern cryptographic protocol design (see Public Key Cryptography). With his student Silvio Micali he built the Blum–Micali generator, turning one-way functions into provably unpredictable pseudorandom bits; with his wife Lenore Blum and Michael Shub came the elegant Blum Blum Shub generator (1986), its security resting on factoring the products now called Blum integers. A second program, program checking (with Sampath Kannan), asked how a fast checker can verify the answers of an untrusted program — work that fed directly into interactive proofs and property testing.

The deepest legacy may be human. Blum’s doctoral students form arguably the most decorated advising tree in computer science: Leonard Adleman (the A in RSA, Turing 2002), Shafi Goldwasser and Silvio Micali (Turing 2012 — see Shafi Goldwasser and Silvio Micali), Michael Sipser, Gary Miller, Umesh and Vijay Vazirani, Russell Impagliazzo, Mor Harchol-Balter, Ryan Williams, Luis von Ahn. His advising method is famous: meet every week, work on what the student burns to understand, and take seriously questions others find naive.

CAPTCHA: The Reverse Turing Test

At Carnegie Mellon, Blum and his graduate student Luis von Ahn took on a complaint from industry: bots were signing up for free email accounts and skewing online polls by the thousands. Their answer inverted Alan Turing’s imitation game — instead of a machine trying to pass as human before a human judge, a machine judge would administer a test that humans pass easily and machines fail: reading mangled text, at the time a reliably human skill. The 2003 paper with Nicholas Hopper and John Langford named it CAPTCHA — Completely Automated Public Turing test to tell Computers and Humans Apart — and made a sly theoretical point: a CAPTCHA is a security primitive built on an open AI problem, so it is win-win — either the attacker fails, or AI has measurably advanced. Von Ahn pushed the idea into reCAPTCHA (2007, acquired by Google in 2009), which harvested the human effort to digitize old books and newspapers, then founded Duolingo on the same humans-as-computation insight.

In 2018, Blum and Lenore Blum — by then both senior CMU professors — resigned from the university in protest over its treatment of Lenore and the entrepreneurship program she had built; the episode made national news in computing circles. Undeterred, the two turned jointly to Manuel’s original question, publishing a formal model of consciousness — the Conscious Turing Machine, a theoretical-computer-science rendering of the global workspace theory — in PNAS in 2022, sixty years after he had set the problem aside as premature.

⚠️ Dead End: The Test That Was Built to Die

CAPTCHA is a rare technology whose obsolescence was part of the design — and it arrived. By the mid-2010s, machine vision read distorted text better than humans; Google’s own researchers cracked the hardest text CAPTCHAs with near-perfect accuracy, and image-grid puzzles (“select all traffic lights”) fell next, with modern multimodal models (see The Generative AI Revolution) solving them faster than people. Each escalation that kept bots out also locked out humans with visual impairments, and cheap human CAPTCHA-solving farms undercut the premise entirely. The industry’s retreat — reCAPTCHA v3 and successors score behavior silently instead of posing puzzles, trading the visible test for pervasive tracking — ended the era of the squiggly word. By Blum and von Ahn’s own win-win accounting, though, the dead end is a graceful one: the test died precisely because AI advanced, and millions of book pages got digitized along the way. The unsolved residue is real: the web still has no good, privacy-respecting answer to “are you human?” — a question getting harder every year.

Fun Fact: A Household of Professors

For years Carnegie Mellon’s computer science faculty included three professors named Blum: Manuel, Lenore (a founder of the Association for Women in Mathematics and of CMU’s Women@SCS), and their son Avrim, a leading learning theorist — likely the only nuclear family ever simultaneously on one top CS faculty. Manuel’s standing advice to them and everyone else: “You are allowed to work on any problem you want — as long as you can’t stop thinking about it.”