Try
A simulator runs a program for 100 steps without seeing it halt. What has it learned? The execution did not halt during those steps. It might halt at step 101, much later, or never. A timeout does not choose between those possibilities. Yet for a counter that decreases through the natural numbers, a mathematical proof can establish termination without observing every step.
The question here is different: could one algorithm always finish and correctly decide eventual halting for every program and input? We will prove that no such algorithm exists in a specified ideal model. This is not a claim that every individual program is mysterious, or that a physical machine literally has infinite memory.
Use deterministic programs described by finite binary strings. Syntax checking terminates and identifies valid program codes. Programs may use arbitrarily much memory as a computation proceeds; no fixed memory cap is imposed. A universal simulator can simulate each instruction of any valid program on a finite binary input. The model supports finite composition, conditional branching and an explicit infinite loop, and is Turing-complete. We also fix an effective, unambiguous encoding of pairs of strings. These are modeling assumptions, not features proved by a browser demonstration.
Predict
Let K consist of encoded pairs (p,x) for which p is valid program code and the program halts on input x. Malformed pair encodings and invalid program codes are outside K. “Halts” includes any terminating outcome; it is not the same as accepting an input or printing a favorable answer.
A decider for K must halt on every finite input and return yes exactly for members, no exactly for nonmembers. A recognizer must eventually accept each member and must never accept a nonmember. On nonmembers it may reject or run forever. Predict which contract a universal simulator satisfies when it accepts as soon as the simulated program halts.
Syntax rejection handles invalid inputs, and successful simulation recognizes a halt. On a valid infinite execution the simulator keeps running. It is a recognizer, not a decider. The missing requirement is total termination, not merely a faster processor.
Experiment
This is a paper construction, not executable learner code. Assume for contradiction that a finite program H is a total correct halting decider. Write a new finite program D:
D(p):
if p is not valid program code:
halt
answer := H(p, p)
if answer is yes:
repeat forever
otherwise:
halt
H receives the encoding of the pair shown. D can contain the finite code of H, a syntax checker, a branch and a loop. Thus under the assumption, D is itself a permitted finite program. Choose a valid binary code d describing it. We, outside the program, now supply d as the input to D. D does not discover its own source: it treats whatever input it receives as data and passes it to H twice.
Complete the consequence column before reading it:
| H’s answer on (d,d) | What correctness claims | What D(d) does |
|---|
| Yes | D(d) eventually halts | Enters its infinite loop |
| No | D(d) never halts | Halts after H returns |
Both rows contradict the claimed correctness of H. There is no third row for “H never answers,” because totality was part of the assumed contract. The invalid-code branch cannot escape the contradiction: d is valid code by construction.
Understand
The diagonal argument rejects the existence of a total correct universal halting decider. It does not reject syntax checkers, bounded simulators, useful incomplete analyzers or proofs about restricted programs. The self-input is legitimate because codes and inputs share a finite-string representation; it is not an instruction requiring supernatural self-knowledge. The contradiction concerns the particular valid pair (d,d), so the chosen convention for other invalid strings does not affect it.
A fixed step budget B defines a different problem: whether a valid run halts within B transitions. Check the initial configuration, simulate at most B transitions and answer from that finite trace. This always finishes. A negative answer settles the bounded question only. To discuss eventual halting honestly, report “not halted within budget” rather than “never halts.”
Now transfer the impossibility to a different question. Let M contain the valid programs that eventually emit a distinguished marker when run on empty input. Given a candidate encoding of (p,x), construct a program Q as follows. For invalid encodings output the code of a fixed silent infinite loop. Otherwise put the finite strings p and x into a wrapper:
Q(any_input):
simulate p on the stored input x
keep all simulated output internal
when that simulation halts:
emit the marker
halt
Writing Q’s code is a finite effective transformation. It does not execute p while constructing the code and does not need to know whether p will halt. The simulation can redirect or store virtual output without emitting it from Q; this prevents a marker printed by p from causing a false positive.
If p halts on x, Q eventually reaches its emitting instruction. Conversely, if Q emits, the simulation must have halted, because that instruction is its only source of output. Invalid source cases emit nothing. Thus the source is in K if and only if the constructed code is in M. This is a mapping reduction from K to M.
If M had a total correct decider, first constructing Q and then applying that decider would decide K. Both stages would finish, and the two-direction equivalence would make their answer correct. Since K has no decider, M has none. The direction matters: solving the target would solve the known impossible source. Merely observing that two problems sound similar proves nothing.
Apply
Repair this proposed reduction: “Run p on x; if it halts, print the code of a program that emits a marker.” Its code-producing stage may run forever. It is not the total transformation required above. The repair is to write a wrapper containing a future simulation, without performing that simulation during construction.
For another changed target, let Q ignore its input and return 0 only after the stored simulation halts. If p halts, Q computes the everywhere-defined constant-zero function. If p does not halt, Q returns on no input. These partial functions differ in their domains, even though they never disagree on a pair of returned values. Explain why equality of partial functions requires matching definedness as well as matching outputs.
Finally suppose both K and its complement had recognizers. Run them in fair alternation, one simulated step each. Exactly one must eventually accept; its acceptance provides the appropriate yes or no decision. This would decide K, contradicting the proof. Therefore the complement is not recognizable. Waiting for the first recognizer to finish before starting the second is not fair alternation and can get stuck forever.
Continue
Keep three different conclusions separate: a particular trace has not finished; a particular program has a proof of termination or nontermination; and no total correct algorithm decides every instance of a problem. “Unknown from this run” is a limitation of current evidence. Undecidability is a theorem about the absence of one universal algorithm under the stated model. It does not say no individual case can be settled.
The six proof tasks require the model contract, both diagonal cases, bounded simulation, both directions of a reduction and its effective construction. They do not run arbitrary programs or certify a general verification tool. The primary scope reference is MIT 18.404J, Fall 2020, Lecture 8: Undecidability, inspected 25 October 2026. That lecture develops diagonalization and reducibility using machine acceptance; this lesson supplies an original halting-and-marker version with its own explicit conventions. It is a focused supplement to the discrete-mathematics sequence, not equivalence to a full theory-of-computation course.
