No algorithm can determine whether an arbitrary program halts — proven by contradiction
Setup: Suppose HALT(P,X) is a program that returns YES if P(X) halts, NO if it loops forever.
We'll construct a program that makes HALT give the wrong answer — a contradiction.
Turing Machine Simulator
Select a simple TM and watch it run. Some halt; some loop forever.
State: q0 | Step: 0
Select a TM and press Run
TM Transition Table
...
Why it's hard:
For simple machines, we can trace execution.
But for arbitrary programs, detecting an infinite loop requires simulating potentially forever.
The Collatz function: does it always reach 1? Still unknown! This is exactly the flavor of the halting problem.
THE CONTRADICTION
Define DIAGONAL(P):
function DIAGONAL(P):
if HALT(P, P) == YES: // if P halts on itself
loop forever // then we loop forever
else: // if P loops on itself
halt // then we halt
Now ask: What does DIAGONAL(DIAGONAL) do?
Case 1: DIAGONAL(DIAGONAL) halts
⟹ HALT(DIAGONAL, DIAGONAL) = YES
⟹ DIAGONAL sees YES
⟹ DIAGONAL loops forever ⟹ Contradiction!
Case 2: DIAGONAL(DIAGONAL) loops
⟹ HALT(DIAGONAL, DIAGONAL) = NO
⟹ DIAGONAL sees NO
⟹ DIAGONAL halts ⟹ Contradiction!
Both cases lead to contradiction ⟹ HALT cannot exist!
The halting problem is undecidable.
Alan Turing, 1936 — "On Computable Numbers, with an Application to the Entscheidungsproblem"