01Overview
Having defined the Turing machine, Turing used it at once to prove the decision problem unsolvable: assume a machine H that decides whether any program P halts on input x; build a program D that halts exactly when H says it does not. The contradiction shows the halting problem is undecidable.
This is more than a technical result. It says some problems are not merely hard — they have no algorithmic solution at all. Rice’s theorem sharpens it: any non-trivial semantic property of programs is undecidable. In practice a compiler cannot decide every infinite loop exactly, static analysis must approximate, and a “clever enough” termination proof always needs a person.
02History
- 1936
The halting problem is undecidable
The diagonal argument, applied to programs.
- 1936
The Entscheidungsproblem has no solution
Hilbert's programme is proved impossible.
- 1953
Rice's theorem
Every non-trivial semantic property of programs is undecidable.
- 1970
Recursion theory takes shape
Computability becomes a branch of its own.
03Core concepts
Decidability
An algorithm exists that answers yes or no for every input in finite time.
Reduction
Turn problem A into problem B so that a solution to B solves A.
Recursively enumerable
A set whose elements a Turing machine can enumerate — wider than decidable.
04Hands-on
Do it once — it beats reading it ten times
Assume halt() exists, construct the contradictory call by diagonalisation, and print each step of the contradiction
05Self-check
Say it in your own words first, then open the answer. Whatever you cannot explain is what to review next.
Can you explain "Decidability"?
An algorithm exists that answers yes or no for every input in finite time.
Can you explain "Reduction"?
Turn problem A into problem B so that a solution to B solves A.
Can you explain "Recursively enumerable"?
A set whose elements a Turing machine can enumerate — wider than decidable.
What problem did it solve, and why was there nothing better at the time?
Go back to the history section: how was this done before, and what did it cost?
If you had to build it today, how would you break it down?
Use the hands-on task above: write a plan of at most three steps before you start.
06Key people
Alan Turing
1912 – 1954
Used the diagonal method to prove the halting problem undecidable.
Emil Post
1897 – 1954
Independently developed computability and the decision problem.
07Further reading
- Computability and Unsolvability