The Halting Problem

Every programmer has stared at a spinning cursor and wondered: is it still working, or stuck in an infinite loop? It feels like something a smart enough tool should be able to tell you. Couldn't a perfect analyzer read any program and announce, before you run it, whether it will eventually stop or loop forever?

That tool is the dream of the halting problem: a single program H that takes any other program and its input, and always answers "halts" or "runs forever" — correctly, every time.

Everywhere else on this site, "hard" has meant slow — problems that take impractically long. The halting problem is a different beast. In 1936 Alan Turing proved that H cannot exist. Not that it's slow, not that we haven't found it yet — that no algorithm can ever decide halting in general. It's our first encounter with a problem that is not hard but impossible.

Try it yourself. Each card shows a tiny program. Predict whether it halts or loops forever, then reveal the answer.

<p class="hint">{{hint}}</p>
<div class="card">
  <div class="counter"><span id="idx">1</span> / <span id="n">0</span> &nbsp;·&nbsp; {{score_label}} <span id="score">0</span></div>
  <pre id="code" class="code"></pre>
  <div class="btns">
    <button id="halts" type="button">{{btn_halts}}</button>
    <button id="loops" type="button">{{btn_loops}}</button>
  </div>
  <div id="verdict" class="verdict"></div>
  <button id="next" type="button" class="next" hidden>{{btn_next}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.card { border: 1px solid #e2e6eb; border-radius: 12px; padding: 1rem; background: #fff; }
.counter { font: 600 13px system-ui; color: #777; margin-bottom: .5rem; }
.code { background: #1d2733; color: #e6edf3; border-radius: 8px; padding: .8rem 1rem; font: 600 13.5px ui-monospace, monospace; line-height: 1.5; overflow-x: auto; white-space: pre; margin: 0 0 .8rem; }
.btns { display: flex; gap: .6rem; }
button { font: 600 14px system-ui, sans-serif; padding: .55rem 1.1rem; border-radius: 8px; cursor: pointer; border: 1px solid #457b9d; background: #457b9d; color: #fff; }
.btns button { flex: 1; }
#loops { background: #fff; color: #457b9d; }
button:disabled { opacity: .5; cursor: default; }
.verdict { min-height: 1.4em; margin: .8rem 0 0; font-size: .95rem; line-height: 1.5; }
.verdict.ok { color: #0a7d33; }
.verdict.bad { color: #c0392b; }
.verdict b { font-weight: 800; }
.verdict .para { color: #6d28d9; }
.next { background: #2a9d8f; border-color: #2a9d8f; margin-top: .8rem; }

// Code not found

Some are obvious. Some hide a subtle infinite loop. And one — the paradox machine at the end — is built so that any halting detector you imagine gives the wrong answer about it. That single counterexample is the whole proof in miniature: assume a perfect detector exists, and you can always construct a program it cannot classify.

The proof is a beautiful piece of self-reference. Suppose a perfect detector H(program, input) exists, returning "halts" or "loops".

• Build a new program T. When given a program P, T runs H(P, P) — asking "does P halt when fed itself?".
• Then T does the opposite: if H says P halts, T loops forever; if H says P loops, T halts.
• Now feed T to itself. Ask: does T(T) halt?
  • If H says T(T) halts, then by its design T(T) loops forever — contradiction.
  • If H says T(T) loops, then T(T) halts — contradiction.

Either way H is wrong about T. Since the only assumption was that H exists, that assumption must be false. No halting detector can exist — the problem is undecidable.

This is deeper than NP-hardness. An NP-hard problem is (probably) slow but solvable in principle; the halting problem has no correct algorithm at any speed. And it's not alone: Rice's theorem extends it — essentially every interesting question about what a program does is undecidable too.

Undecidability isn't an abstract curiosity — it draws the boundary of what software tools can promise:

• No perfect bug finder. A tool that always decides whether code crashes, leaks memory or loops forever would solve halting. So every analyzer must approximate.
• Compilers and static analysis flag some infinite loops and dead code, but never all — they trade completeness for soundness.
• Formal verification proves programs correct only by restricting to decidable fragments or accepting human-guided proofs.
• Antivirus can't perfectly decide whether arbitrary code is malicious; detection is always heuristic.
• Termination provers (like Microsoft's Terminator) succeed on many real programs, but no tool can succeed on all.

The lesson tools live by: aim for "usually right and never wrongly certain", because "always right" is off the table.

The halting problem marks a frontier the rest of this site only hints at. Hard problems are about time — we might wait centuries, but an answer exists. The halting problem is about possibility: for some questions, no procedure can ever give the right answer, no matter how fast the machine or how clever the programmer.

Remarkably, Turing found this ceiling in 1936, before a single electronic computer had been built — defining the limits of computation in the very act of defining computation itself. It's a humbling and oddly beautiful result: the machines we built to answer questions come with a list, fixed forever, of questions they can never answer.