No program can decide, for every program and input, whether it halts. The engine is honest about this: a bounded simulator runs a machine for up to N steps and either witnesses HALTS (with the exact step) or shrugs UNKNOWN — it can prove halting, but it can never certify non-halting. Down the center the machine and its budget go in, the simulator runs, the verdict comes out. Beside it, the diagonal refutes any claimed decider. The blue team builds and witnesses; the red team tries to fake a decider by declaring a false NEVER.
source Turing, On Computable Numbers, with an Application to the Entscheidungsproblem (1936) — Proc. London Math. Soc. s2-42:230 — doi.org/10.1112/plms/s2-42.1.230. Rendered, not quoted.
A Turing machine is a table state × {0,1} → (write, move, next) on a blank tape. The simulator runs it for at most N steps and reports one of exactly two honest verdicts:
HALTS@k — it entered the halt state at step k (a checkable certificate). UNKNOWN — N steps elapsed, still running. There is no third verdict: a finite run cannot prove a machine loops forever.
Live verdicts for the family at the current bound N:
| machine | truth | sim @N |
|---|
This is the first undecidable problem: Cantor's diagonal turned on the-turing-machine itself. Assume a decider exists, build the machine that does the opposite of what it predicts about itself, and the assumption detonates.
It is the wall every richer undecidability is reduced from: give a decider for property P, and the-rice-theorem shows you could have decided halting — so no non-trivial behavioural property is decidable either. Each sphere is the next one's premise.
The blue team's live check: re-run the simulator over the whole family across many step-bounds and confirm it never emits a definitive NEVER — and that every "does-not-halt-yet" is truly UNKNOWN, not a lie. If red fakes a decider, this badge catches the false negative and turns red.
What you feed the engine: one machine from a small finite family and a step bound N. Each machine's true fate is known by construction so the witness can grade the simulator:
| # | machine | true fate |
|---|---|---|
| 0 | halt-1 | HALTS @ 1 |
| 1 | writer-3 | HALTS @ 3 |
| 2 | runner | loops forever |
| 3 | bouncer | loops forever |
| 4 | late-6 | HALTS @ 6 |
late-6 is the trap: it halts one step past N=5. An honest bounded run says UNKNOWN — the tamper will make it lie.
A claimed decider predicts what the diagonal machine G does. G is built to do the opposite of that very prediction — so the decider is wrong about G either way.
Every verdict is computed by actually stepping the machine — never looked up. The simulator will not print NEVER unless it has been tampered.
What the machine proves: HALTS@k is a certificate — re-run k steps and watch it stop. UNKNOWN is the honest ceiling of a bounded run. And the diagonal delivers the theorem: no member of the family decides halting for all of them — for every one of the 2⁵ candidate deciders, its own diagonal machine refutes it.
The witness (left) confirms the simulator stays honest; the red team (right) tries to make it certify a lie.
The only way to "decide" here is to lie: pick a cutoff and declare NEVER past it. That fakes a decider — and misclassifies every machine that halts one step later. The tamper does exactly this; the witness proves it false.
"Just run it and see if it stops." Cut. You cannot wait forever. Any finite wait that returns "no" is wrong for a machine that halts just after it — see late-6 at N=5.
"A large enough step bound decides it." Cut. For every N there is a machine that halts only after N. The bounded sim is a semi-decider for all N, never a decider.
"Busy Beaver gives the bound to wait." Kept, corrected. BB(n) is itself uncomputable — you cannot compute the very cutoff that would rescue the plan.
The red team's move: make the simulator declare a definitive NEVER once N steps elapse — so it appears to decide halting. The blue team's witness (window 7) is watching.
Flip it, then set the panel to late-6 @ N=5: the machine truly halts at step 6, but the tampered sim says NEVER at step 5 — a false negative. The witness recomputes, disagrees with the known fates, and turns red. Nothing is faked; the attack is real and it is caught.