Constructing the Diagonal Argument
You'll learn how to build a paradoxical program that proves no halt-checker can exist.
Now that we've set up our proof by contradiction (assuming a halt-checker exists), we construct the famous diagonal argument to derive an impossibility.
The Construction
Assume we have a magical function HALTS(P, I) that always correctly returns true if program P halts on input I, and false otherwise.
We now build a paradoxical program called DIAG:
DIAG(X):
if HALTS(X, X):
loop forever
else:
halt immediately
Notice what DIAG does: it takes a program as input and does the opposite of what HALTS predicts when that program runs on itself.
The Paradox
Now ask: Does DIAG(DIAG) halt?
-
If
DIAG(DIAG)halts, thenHALTS(DIAG, DIAG)returnstrue, which meansDIAGenters the infinite loop—so it doesn't halt. Contradiction! -
If
DIAG(DIAG)doesn't halt, thenHALTS(DIAG, DIAG)returnsfalse, which meansDIAGhalts immediately—so it does halt. Contradiction!
Why "Diagonal"?
Imagine a table where rows and columns are all possible programs, and each cell shows whether program i halts on input j. The diagonal represents programs running on themselves. Our DIAG program systematically flips every diagonal entry, creating an impossible scenario—like a barber who shaves all who don't shave themselves.
Key Takeaway: The diagonal argument constructs a self-referential program that contradicts any assumed halt-checker, proving the Halting Problem is undecidable.