Why can no machine ever settle every question in mathematics?
In 1936 Alan Turing proved that one simple question, "will this program ever stop?", is one no computer can always answer.
▶ Start the storyBecause some questions trap any machine that tries to answer them. In 1928 David Hilbert and Wilhelm Ackermann asked for an algorithm that could take any logical statement and answer "yes" or "no": is it valid? This was the Entscheidungsproblem, the "decision problem". In 1936 Alonzo Church and Alan Turing each proved that no such algorithm can exist.
Turing's route is the one that stuck, because it is about machines. He showed that a perfect math-deciding machine would also let you answer a simpler-sounding question: given any program and its input, will it eventually stop, or run forever? Today this is called the halting problem. Then he showed that question has no general answer.
The proof is a beautiful trap. Suppose someone hands you a program that always correctly predicts whether a program halts. Build a contrary program that asks the predictor about itself, then does the opposite: if the predictor says "you will stop", it loops forever; if the predictor says "you will loop", it stops at once. Now ask the predictor about the contrary program. Whatever it answers is wrong. So the perfect predictor cannot exist. The trick is a cousin of Cantor's diagonal argument about infinities.

This was a blow to Hilbert, who as late as 1930 believed no problem was unsolvable and whose slogan was "we must know, we will know". It does not mean we can't ever tell whether programs stop: simple cases are easy, and real tools prove that particular programs finish. It means no single method works for every case.
Step 1: Assume a perfect predictor H
It says whether any program halts on any input.
Step 2: Build Contrary
It asks H about a program run on its own code, then does the opposite.
Step 3: Feed Contrary to itself
If H says "halts", it loops; if H says "loops", it halts.
Step 4: Contradiction
H is wrong either way, so H cannot exist.
Quiz me
0/3
Recap
Any would-be halting predictor can be fooled by a program that asks it about itself and does the opposite.
Surprising fact · Turing never used the word "halting": the name "halting problem" appeared around 1952.
Sources (6)
No source, no claim. Every fact in this lesson (26 claims) cites at least one of these.