The Halting Problem

No algorithm can decide, for every program and input, whether that program eventually halts or runs forever.

The question

Given the source code of a program and an input, will the program eventually stop, or will it loop forever? The halting problem asks for a single algorithm that answers this correctly for every program-input pair. Turing proved in 1936 that no such algorithm exists.

The contradiction

Suppose a decider H exists that returns "halts" or "loops" for any program P on input x. Build a new program D that takes a program P, runs H on P applied to itself, and then does the opposite: if H says P halts, D loops; if H says P loops, D halts. Now ask what D does on itself.

def D(P):
    if H(P, P) == 'halts':
        while True: pass   # loop forever
    else:
        return           # halt

If H says D halts on D, then D loops, contradicting H. If H says D loops on D, then D halts, contradicting H again. Either way H is wrong, so H cannot exist.

Why it is only recognizable

You can always confirm halting: run the program and wait. If it stops, you have your yes. But non-halting can never be confirmed by waiting, because no finite wait proves it never stops. So the problem is recognizable but not decidable.

Consequences

• No perfect infinite-loop detector for arbitrary code can exist
• No tool can verify all non-trivial program properties in general (Rice's theorem)
• Practical analyzers must be conservative: sound but incomplete

What it does not mean

It does not mean we can never tell if a specific program halts. Many programs are easy to analyze. The impossibility is about a single method that works for all cases. Real static analyzers handle common patterns and give up or approximate on the rest.