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

The Contradiction Emerges

Show how the constructed program leads to a logical contradiction, proving undecidability.

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 "P halts on itself," then DIAGONAL loops forever
  • If HALT(P, P) says "P loops on itself," then DIAGONAL halts 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 means HALT(DIAGONAL, DIAGONAL) said it would loop forever. But it actually halted—so HALT was wrong.

  • Case 2: Suppose DIAGONAL(DIAGONAL) loops forever. By construction, this means HALT(DIAGONAL, DIAGONAL) said it would halt. But it's looping—so HALT was 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.