Course contentsShow
← Computer Science
Lesson 1881 of 2,87242. Turing Machines and ComputabilityFree lesson

Constructing the Diagonal Argument

Build the diagonal argument: assume a halt-checker exists and construct a paradoxical program.

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, then HALTS(DIAG, DIAG) returns true, which means DIAG enters the infinite loop—so it doesn't halt. Contradiction!

  • If DIAG(DIAG) doesn't halt, then HALTS(DIAG, DIAG) returns false, which means DIAG halts 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.