The halting problem (Turing) — the limits of computers

What just happened?

For program A (“count to 100”) you can see at once that it halts. For program B (“while true”) — that it runs forever. But for program C (“search for a counterexample to some hypothesis”) it is unknown: if a counterexample exists, the program finds it and stops; if none exists — it searches forever. And we cannot tell in advance which case holds.

The halting problem

This is a fundamental result of theoretical computer science, proved by Alan Turing in 1936 — in the very paper that defined the Turing machine, a mathematical model of a computer. The question is: can you write a single universal program (a detector $H$) that, for ANY other program $P$ and its input, decides whether $P$ ever halts or runs forever?

Proof by contradiction (self-reference)

Turing proved that such an $H$ does not exist. The proof is ingenious and contrarian — in the spirit of Russell’s paradox. Suppose $H$ exists. Let us build from it a contrarian program $D$ that does the OPPOSITE of what the detector claims:

Now let us run $D$ on itself — $D(D)$:

We obtain a self-contradiction: if the detector claims that $D(D)$ halts, then $D$ deliberately enters a loop (does not halt) — and vice versa. Since the assumption that $H$ exists leads to a contradiction, such a program cannot exist. The halting problem is UNDECIDABLE (undecidable).

What does it mean in practice?

The consequence is profound: there are problems that are fundamentally uncomputable — that no computer, however infinitely fast, will ever solve. It is not a matter of “too little power”, but a fundamental limit on what algorithms can achieve. That is why you cannot write a program that perfectly detects all viruses, all bugs in someone else’s code or all infinite loops.

Why this matters for your exams:

Turing’s discovery — alongside Gödel’s incompleteness theorems — mapped out the limits of mathematics and computer science, and at the same time laid the foundations of all computing (Turing is regarded as its father). This extends the topic of computability: the very scheme of proof by contradiction and the diagonal argument (self-reference) are classic tools of logic and set theory.

Remember: there are algorithmically undecidable problems — no program solves the halting problem for all possible programs. It is not a lack of computing power, but a hard, mathematical limit of computability.