Core argument
Some limits are not engineering problems — they belong to the definition of computing itself. This piece walks through Turing's proof that no universal procedure can decide whether an arbitrary program halts, and why that result still marks the practical line between problems worth solving exactly and problems to approximate.
Counter-intuitive point
The same paper invented the universal machine and proved its blind spots — and the aftershock reached far beyond exotic self-referential programs. See the outline's "Cold showers" and "Rice's theorem" sections.
What to do next
When a problem reduces to halting, stop hunting for a universal algorithm and look for the restricted or approximate version — the outline's if-then rules give you the decision procedure.
Connections
A sister piece to Gödel's Incompleteness Theorems (2026-10-09): two 24-year-olds, one line of argument — formal systems and computers hit the same wall from opposite sides.
The 24-Year-Old Who Proved Computers Can't Do Everything
Why this matters: the twin question
Gödel at 24 showed formal systems have blind spots; Turing at 24 showed computers have things they cannot compute
Same line, two sides: is the boundary of formal systems the same line as the boundary of computability?
If you claim “computers can compute anything with enough power,” this paper is the rebuttal
1936: one paper, two revolutions
"On Computable Numbers, with an Application to the Entscheidungsproblem" — submitted May 1936, published January 1937 in the Proceedings of the London Mathematical Society
Target: Hilbert's Entscheidungsproblem (1928) — decide, by a fixed mechanical procedure, whether any given mathematical statement is true
Invention: the universal machine — reads another machine's description as input and simulates it; program and data share one tape → the stored-program principle
Cold fact: the same paper that invented the computer also proved its permanent blind spot
The proof in plain words: diagonalization
Assume a halt-checker H(P, I) that always correctly answers whether program P halts on input I
Build a trickster program D: on input X, ask H what D(X) does — then do the opposite (halt if H says "loops", loop if H says "halts")
Feed D its own description: D(D) halts exactly when H says it loops — contradiction either way, so H cannot exist
No assumption about speed or cleverness was used: the limit is logical, not engineering
Three cold showers: what the theorem does NOT spare
Quantum computers: undecidable stays undecidable — quantum computing is not hypercomputation
AI and future tricks: no learned oracle can decide halting in general; it can only guess well on restricted cases
Human intuition: Gödel considered only Turing's definition of "mechanical procedure" to be genuinely adequate
Who got there first: the 1936 priority race
Church, April 1936: first undecidability proof of the Entscheidungsproblem, via λ-calculus — months before Turing
Gödel's verdict: only Turing gave a genuine definition of a mechanical procedure
The Church–Turing thesis: every effectively calculable function is Turing-computable — still a thesis, not a theorem
The name "halting problem" was coined by Martin Davis in 1952 — sixteen years after the proof
Rice's theorem, 1951: the practical aftershock
Henry Rice's doctoral dissertation (Syracuse, 1951; journal version 1953): any non-trivial semantic property of programs is undecidable
Semantic = about what the program DOES (halts? bug-free? malicious?); syntactic = about how the code looks (contains an if)
Consequence: a perfect antivirus — a universal "is this program malicious?" checker — is impossible in principle
What survives: sound-but-incomplete checkers and approximations — perfection is what dies, usefulness is not
Common mistakes: read this before arguing
Mistake 1: "More computing power will fix it" — the proof uses no resource assumption at all
Mistake 2: "Undecidable means very hard" — no: hard problems (NP-complete) still have algorithms, just slow ones; undecidable means NO algorithm exists
Mistake 3: "It only matters for weird self-referential programs" — Rice shows it bites ordinary properties: correctness, safety, equivalence
What you can do: the decidable–undecidable map
Decidable, keep the algorithm: regular-language membership, type checking, syntax analysis
Undecidable, stop hunting: halting, program equivalence, "does it print this output?", any non-trivial semantic property
IF-THEN 1: when your problem reduces to halting → stop searching for a universal algorithm; ship an approximation or restrict the inputs
IF-THEN 2: when someone demos a "perfect" analyzer → ask which restriction buys decidability — linters, type systems and sandboxes all pay in some currency
IF-THEN 3: when scoping an AI coding agent → cap undecidable ambitions: aim for "usually right on this repo", never "provably right on all programs"