The halting problem

Parent: turing-machines

The first — and most-reduced-from — undecidable problem: there is no algorithm that decides, for an arbitrary program and input, whether it halts.

Undecidability of halting

No Turing machine decides, for arbitrary (M, x), whether M halts on input x.

Proof

Suppose a machine H(M,x) always halts and correctly answers "does M halt on x?". Build D(M): run H(M,M); if it says "halts", loop forever; if "doesn't halt", halt. Now feed D its own code and ask about D(D):

if H(D,D) = "halts", then by construction D(D) loops — so it does not halt;

if H(D,D) = "doesn't halt", then D(D) halts. Either way H is wrong on (D,D). So H cannot exist. ∎

It's the same diagonal / self-reference move as Cantor, Russell, and Gödel: build the object that does the opposite of what's predicted about itself.

Consequences — undecidability spreads by reduction

Rice's theorem: every non-trivial semantic property of a program (of what it computes) is undecidable — halting is just the first domino (recursively-enumerable-languages).
Reductions: "does M ever print 0?", "do two programs compute the same function?", the Entscheidungsproblem (history), Post's correspondence problem, generalized Collatz — all shown undecidable by reducing halting to them.
One-sided: halting is recognizable but not decidable — you can confirm halting (wait), never confirm non-halting.

Ties to the thread

"Does this iteration/agent converge / terminate?" is the halting problem in disguise — undecidable in general (recursion-is-a-phase-transition). You recover a usable answer only by relaxing (a termination certificate / ranking function, a tolerance, a horizon). The uncomputable growth of the wait time is the busy-beaver.