Introduction

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.

Halts or Loops?

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

<p class="hint">Read each tiny program and predict: does it <b>halt</b> (stop) or <b>loop forever</b>? Click your guess, then reveal the answer. The last one is special.</p>
<div class="card">
  <div class="counter"><span id="idx">1</span> / <span id="n">0</span> &nbsp;·&nbsp; score <span id="score">0</span></div>
  <pre id="code" class="code"></pre>
  <div class="btns">
    <button id="halts" type="button">Halts</button>
    <button id="loops" type="button">Loops forever</button>
  </div>
  <div id="verdict" class="verdict"></div>
  <button id="next" type="button" class="next" hidden>Next program →</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// A halting guessing game. The first programs are decidable by eye; the last is the diagonalization "paradox machine" that defeats ANY would-be halting detector H — the heart of Turing’s 1936 proof.
const PROGS = [
  { code: "x = 0\nwhile x < 10:\n    x = x + 1\nprint(x)", halts: true,
    why: "x climbs 0→10 and the loop stops. Clearly halts." },
  { code: "x = 1\nwhile x > 0:\n    x = x + 1", halts: false,
    why: "x only grows, so x > 0 is always true. Loops forever." },
  { code: "n = 27\nwhile n != 1:\n    if n % 2 == 0: n = n // 2\n    else: n = 3*n + 1", halts: true,
    why: "This is the Collatz sequence from 27 — it does reach 1 (after 111 steps). Halts. But whether it halts for EVERY n is an open problem no one can prove!" },
  { code: "while True:\n    pass", halts: false,
    why: "An explicit infinite loop. Loops forever." },
  { code: "for i in range(1000000):\n    pass\nprint('done')", halts: true,
    why: "A finite, if long, loop. Halts." },
  { code: "# The paradox machine T(T):\n#   if H says T halts -> loop forever\n#   if H says T loops -> halt\nrun_opposite_of( H(T, T) )", halts: null,
    why: "There is no right answer — and that’s the point. Whatever a perfect detector H predicts about this self-referential program, T is built to do the opposite. H must be wrong about T. So H cannot exist: halting is undecidable." }
];

let i = 0, score = 0, answered = false;
const $ = id => document.getElementById(id);

function show() {
  answered = false;
  const p = PROGS[i];
  $('idx').textContent = i + 1;
  $('n').textContent = PROGS.length;
  $('score').textContent = score;
  $('code').textContent = p.code;
  $('verdict').textContent = '';
  $('verdict').className = 'verdict';
  $('next').hidden = true;
  $('halts').disabled = false;
  $('loops').disabled = false;
}

function answer(guessHalts) {
  if (answered) return;
  answered = true;
  const p = PROGS[i];
  $('halts').disabled = true;
  $('loops').disabled = true;
  const v = $('verdict');
  if (p.halts === null) {
    v.className = 'verdict';
    v.innerHTML = fmt('<b class="para">The paradox machine.</b> %why%', { why: p.why });
  } else {
    const correct = guessHalts === p.halts;
    if (correct) score++;
    v.className = 'verdict ' + (correct ? 'ok' : 'bad');
    v.innerHTML = fmt('<b>%v%</b> It %v2%%why%', { v: correct ? 'Correct!' : 'Not quite.', v2: p.halts ? 'halts. ' : 'loops forever. ', why: p.why });
  }
  $('score').textContent = score;
  if (i < PROGS.length - 1) $('next').hidden = false;
  else { $('next').hidden = false; $('next').textContent = 'Start over ↺'; }
}

$('halts').addEventListener('click', () => answer(true));
$('loops').addEventListener('click', () => answer(false));
$('next').addEventListener('click', () => { i = (i + 1) % PROGS.length; if (i === 0) score = 0; $('next').textContent = 'Next program →'; show(); });
show();
Result
Console

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.

Why It's Impossible

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/halting-problem/Content licensed under CC BY-NC 4.0.