The Contradiction Emerges
What you'll learn: You'll see how the diagonal argument creates an impossible situation that proves no algorithm can solve the Halting Problem.
The Final Step of the Proof
We've constructed a special program in our diagonal argument. Let's call it DIAGONAL. This program takes another program P as input and does the opposite of what a hypothetical halting-decider HALT predicts:
- If
HALT(P, P)says "Phalts on itself," thenDIAGONALloops forever - If
HALT(P, P)says "Ploops on itself," thenDIAGONALhalts immediately
Now here's the kicker: What happens when we feed DIAGONAL to itself?
The Logical Trap
Ask the question: Does DIAGONAL(DIAGONAL) halt?
-
Case 1: Suppose
DIAGONAL(DIAGONAL)halts. By construction, this meansHALT(DIAGONAL, DIAGONAL)said it would loop forever. But it actually halted—soHALTwas wrong. -
Case 2: Suppose
DIAGONAL(DIAGONAL)loops forever. By construction, this meansHALT(DIAGONAL, DIAGONAL)said it would halt. But it's looping—soHALTwas wrong again.
Both possibilities lead to a contradiction! The program HALT must be wrong in either case.
What This Means
Since assuming HALT exists creates an impossible situation, HALT cannot exist. No algorithm can correctly decide whether arbitrary programs halt on arbitrary inputs. The Halting Problem is undecidable.
This is like asking "Does the barber shave himself?" when the barber shaves exactly those who don't shave themselves—there's no consistent answer.
Key Takeaway: The diagonal construction forces any supposed halting-decider into self-contradiction, proving the Halting Problem is undecidable and establishing fundamental limits on computation.