Halting problem — undecidability proof by diagonalization

WHAT is the Halting Problem?

WHY do we care? Many real questions — "does this loop terminate?", "is this code dead?", "are these two programs equivalent?" — reduce to halting. If halting is unsolvable, those are too. It marks the hard limit of what mechanical computation can ever achieve.

HOW the proof works — derivation from scratch

We use proof by contradiction + diagonalization (Cantor's trick that there are "more" reals than integers, repurposed for programs).

Step 1 — Assume the decider exists

Suppose a program H solves halting. Define it precisely:

$H(P, w) = \begin{cases} \texttt{HALT} & \text{if } P \text{ halts on } w \\ \texttt{LOOP} & \text{if } P \text{ runs forever on } w \end{cases}$

Why this step? We want to disprove "H exists." The cleanest route is to assume it does and squeeze a contradiction out — that forces the assumption to be false.

Key fact we rely on: a program is just a string, so we can feed a program its own code as input. (This is what "self-reference" means here.)

Step 2 — Build a troublemaker program D (the diagonal)

Using H as a subroutine, construct:

D(P):                # P is the source code of a program
    if H(P, P) == HALT:   # would P halt when given its own code?
        loop forever
    else:                 # H says P loops on itself
        halt

Why this step? D is engineered to do the opposite of what H predicts about a program running on itself. This deliberate flip is the diagonalization: we'll later place D on the "diagonal" against itself.

Step 3 — Feed D its own code: run D(D)

Ask: does D halt on input D? Two cases, both fatal.

• Case A: Suppose D(D) halts. Then inside D, the branch taken must have been the else (the "halt" branch). That branch runs only when H(D, D) == LOOP, i.e. H claims D(D) runs forever. But we assumed it halts. Contradiction.

• Case B: Suppose D(D) loops forever. Then the if-branch was taken, which happens only when H(D, D) == HALT, i.e. H claims D(D) halts. But we assumed it loops. Contradiction.

$D(D)\text{ halts} \iff H(D,D)=\texttt{LOOP} \iff D(D)\text{ loops}$

A statement equivalent to its own negation is impossible.

Step 4 — Conclude

Every consistent answer leads to contradiction, so our only assumption — that H exists — must be false.

WHY it's called diagonalization

Worked examples

Common mistakes (steel-manned)

Flashcards

Connections

• Turing Machines — the formal model in which "program" and "decide" are defined.
• Decidable vs Recognizable Languages — $HALT$ separates these two classes.
• Reductions and Mapping Reducibility — how undecidability propagates (Example 2).
• Rice's Theorem — generalizes: every nontrivial semantic property of programs is undecidable.
• Cantor's Diagonal Argument — the set-theory ancestor of this proof.
• Universal Turing Machine — why a program can run another program (and itself).
• Church–Turing Thesis — why "no program" means "no possible algorithm at all."

Concept Map

Hinglish (regional understanding)