Halting problem
The undecidable problem of determining whether an arbitrary program terminates or loops infinitely. Proving the halting problem is uncomputable demonstrates fundamental limits of computation. Proof by contradiction shows no algorithm can solve it for all programs. The halting problem exemplifies computability boundaries.
Real World
In 2016, a student's infinite loop in a Python script crashed a university server for hours — no automated system could have predicted this in advance, because the halting problem proves it is impossible to build a general-purpose 'will this code finish?' checker.
Exam Focus
Structure the proof by contradiction clearly: assume H exists, construct paradox function G, show contradiction, conclude H cannot exist.
How well did you know this?