Computability theory — also called recursion theory — asks which mathematical problems can in principle be solved by any algorithm running on any computer with unlimited time and memory, and which cannot. Problems in the second category are not merely unsolved or computationally expensive; they are provably unsolvable by any mechanical procedure whatsoever. The field was founded simultaneously by Alan Turing, Alonzo Church, and Kurt Gödel in 1936, and forms the theoretical bedrock of computer science.
People often assume that with enough computing power, any mathematical problem can eventually be solved. Computability theory proves this false. Some problems are undecidable — not just currently unsolved, but provably unsolvable by any algorithm, any computer, any mechanical procedure, now or ever, regardless of how powerful the machine or how long it runs.
Turing's proof is a beautiful self-referential argument. Assume, for contradiction, that a halting-checker H exists. Build a new program P that uses H on itself: if H says P halts, P runs forever; if H says P runs forever, P immediately halts. Either way, H gives the wrong answer for P — a contradiction. Therefore H cannot exist. The argument is closely related to Cantor's diagonal argument and Gödel's incompleteness proof in its underlying logical structure.
Undecidability is not about computational speed or memory. An undecidable problem cannot be solved even with infinite time, infinite memory, and any conceivable hardware — because the obstacle is logical, not physical. The halting problem is not hard; it is impossible, in a provable, absolute sense.
A Turing machine is a mathematical model of computation consisting of an infinite tape (memory), a read/write head, a finite set of states, and a transition table specifying what the head does (read a symbol, write a symbol, move left or right, change state) based on its current state and the symbol it reads. Despite its simplicity, every known physical computation device — from pocket calculators to supercomputers to quantum computers — can be simulated by a Turing machine (with appropriate encoding). This universality is the content of the Church-Turing thesis: Turing machines capture the full, correct notion of mechanical computation.
A problem is decidable (recursive) if there is a Turing machine that always halts and gives the correct yes/no answer for every input. It is semi-decidable (recursively enumerable) if there is a Turing machine that halts with "yes" on every yes-input, but may run forever on no-inputs. The halting problem is semi-decidable (you can run the program and output "yes" when it halts) but not decidable (you cannot reliably output "no" when it doesn't). The complement of the halting problem — detecting programs that run forever — is neither decidable nor semi-decidable.
Rice's theorem (1953) dramatically extends the halting problem: every non-trivial property of the behaviour of a program (as opposed to its syntactic form) is undecidable. Does this program ever output "hello"? Is this program equivalent to another? Does this program always terminate? All undecidable, by Rice's theorem — a sweeping result showing that undecidability is not an isolated oddity but a pervasive feature of reasoning about programs in general.
Undecidable problems are not all equally hard — they form a rich, precisely calibrated hierarchy. The arithmetical hierarchy classifies problems by the logical complexity of the formula defining them (alternating quantifiers ∀ and ∃). The halting problem sits at level Σ₁; its complement at Π₁; higher levels involve more quantifier alternations and correspond to increasingly hard problems, none solvable by any Turing machine.
Even among undecidable problems, some are "harder" than others in a precise sense. Problem A is Turing reducible to problem B if a Turing machine with access to an oracle for B (a black box that answers B-queries instantly) can decide A. This defines an equivalence relation (Turing equivalence) whose equivalence classes are called Turing degrees. The Turing degrees form a rich, partially ordered structure — an enormously complex object studied extensively since the 1940s. The halting problem defines the degree 0' ("zero jump"); iterating the jump operation gives 0'', 0''', and so on, each strictly harder than the last.
The single most important technical tool in computability theory is the priority method (injury method), invented independently by Friedberg and Muchnik in 1957 to solve Post's problem (whether there exists a Turing degree strictly between 0 and 0'). The priority method constructs computably enumerable sets by simultaneously satisfying infinitely many requirements, with a careful priority ordering to handle conflicts between requirements injuring each other's satisfaction. The method has since been vastly generalised and remains the central technical machinery of the field.
Computability theory and Gödel's incompleteness theorems are deeply connected: the set of theorems provable in Peano arithmetic is computably enumerable (you can enumerate all proofs), but not decidable (you cannot decide provability in general). More precisely, the set of true statements of arithmetic that are not provable in Peano arithmetic is exactly as hard as the Π₁ level of the arithmetical hierarchy — showing that unprovability and undecidability are not merely analogous but formally equivalent in a precise technical sense. This connection was essentially already present in Gödel's 1931 paper and was made fully explicit by Turing, Church, and Kleene in the years immediately following.