A program can answer some questions about other programs. For instance, running a program on an input and observing it stop proves that this particular run halts. But waiting without seeing a stop does not tell us whether it will stop later. The central question is whether one algorithm can always settle every instance, including those on which a simulated program runs forever.
We will prove a negative result under a precise model of computation, then use a reduction to prove a second problem undecidable. The proof does not say that every instance is hard or that a person can never determine the behavior of a particular program. It says that no single correct algorithm halts with the right answer on all encoded instances.
Recognizing is different from deciding
Fix a standard effective encoding of Turing machines as finite strings. We can check syntactically whether a string is a valid encoding and simulate a machine one step at a time. Write for an encoding of , and for an effectively decodable encoding of the pair.
Definition 5.2.1
(Decider and recognizer)
A decider for a language halts on every input and accepts precisely the strings in ; on all other inputs it halts and rejects. A recognizer accepts every string in and accepts no string outside , but it may run forever on an input outside .
Thus every decider is a recognizer, but the definitions do not require a recognizer to signal a negative answer. “Not accepted yet” and “rejected” are different observations.
Definition 5.2.2
(The halting language)
The halting language is
Here halting includes either acceptance or rejection by ; it does not mean acceptance alone. A malformed encoding is outside this language and can be rejected by a syntactic check.
Common mistake
(Halting is not acceptance)
It is tempting to read as the set of pairs on which accepts. But a machine that rejects immediately has halted, so . The set of pairs that accepts is a different language.
Worked example 5.2.3
(A recognizer can confirm a positive instance)
Given a valid pair , simulate on . If the simulation stops, accept. When does stop, the recognizer eventually accepts; when runs forever, the recognizer also runs forever. It never falsely accepts a nonhalting pair. This recognizes but, as the next argument proves, cannot be repaired into a decider that works for every pair.
Assume a perfect halting decider and reverse its answer
Theorem 5.2.4
(Undecidability of the halting problem)
There is no decider for : no Turing machine halts on every input and accepts exactly the strings for which halts on .
Proof
(The diagonal machine contradicts any halting decider)
Suppose for contradiction that a decider exists. On every valid pair , it halts and returns yes exactly when halts on ; otherwise it returns no.
Construct a machine taking one string as input:
- If is not a valid machine encoding, reject.
- Run on the pair where .
- If says
yes, loop forever. If saysno, accept immediately.
is a legitimate machine: validity checking, pairing and the call to are effective, and the final two branches are explicit. Its own finite encoding is therefore a valid input to it.
Run on . It asks whether halts on . Because is assumed to be a decider, this call must return either yes or no.
If returns yes, correctness of says that halts. But the definition of then makes that very run loop forever. If returns no, correctness says the run does not halt, yet immediately accepts and therefore halts. Each possible answer contradicts the assumed correctness of .
Consequently no such decider exists and is undecidable. The recognizer above still exists: undecidable means no total correct decider, not that positive instances cannot be recognized.
Proof X-ray
Where the diagonal proof uses its hypotheses
Totality of is used to make step 2 of return an answer at all. If could run forever on , then would simply fail to halt on , and that is not a contradiction. Correctness of is used on exactly one pair, . The non-obvious move is to feed its own code, so that is asked to predict itself, and then to make do the opposite of the prediction. The argument closes because the two possible answers exhaust what a total can say, and each contradicts correctness.
The self-reference is not an instruction to guess an impossible output. Machines and their inputs are strings in the same effective coding system; receives its own already valid encoding as data. The contradiction depends on always terminating and being correct for this pair. If either promise is removed, the argument no longer gives the same conclusion.
Worked example 5.2.5
(Refuting two concrete candidate deciders)
Take the candidate that answers no on every pair, and let be the diagonal machine built from it. On a valid encoding receives no and accepts, so halts on , while claimed no for the pair . Now take that answers yes on every pair. The machine built from it loops forever on every valid encoding, in particular on , while claimed that it halts. Each candidate is wrong on the diagonal input of its own diagonal machine. Edge case: on a string that is not a valid encoding, both and simply reject; the refutation uses only the diagonal input.
Counterexample mode
A time limit does not decide halting
For a fixed positive integer , a proposed test simulates for steps and reports no if it has not stopped. A machine can simply perform steps of harmless work and then halt. The test answers no on this halting instance. Increasing the fixed limit changes the counterexample; it does not make the test universally correct.
Reduction: change the input, preserve the answer
Consider a seemingly narrower language:
Definition 5.2.6
(Many-one reduction)
A many-one reduction from a language to a language , written , is a total computable function on strings such that
The construction has to produce the new instance without knowing whether the old answer is yes. If a decider for existed, compute , run that decider, and return its answer; both stages halt, giving a decider for .
Theorem 5.2.7
(Empty-input halting is undecidable)
The map constructed below is a many-one reduction . Consequently is undecidable.
Proof
(Reduction from arbitrary-input halting to empty-input halting)
For a valid , effectively construct a machine that ignores its own input and simulates on the fixed string . Such code can be generated mechanically by embedding the finite descriptions of and into a simulation wrapper. Set
For malformed , output the encoding of a fixed machine that loops forever. This makes total and preserves the fact that malformed strings are not in .
On empty input, halts exactly when halts on . Therefore
Thus . A hypothetical decider for would decide by the procedure above, contradicting the diagonal argument. Hence is undecidable.
Proof X-ray
Why the reduction map only writes code
The map writes the code of and never runs : if building required knowing whether halts on , the reduction would already solve the halting problem. Totality of explains the malformed branch, since the decider for built from must handle every string. The equivalence is used in both directions: a halting run of on is a halting empty-input run of , and a nonhalting run stays nonhalting. Finally, the direction is essential: it is the undecidability of the source , from the diagonal argument, that is transferred to the target .
Common mistake
(Reducing in the wrong direction)
The arrow direction matters. We transformed the already-known hard problem into the proposed target. Merely showing would not prove undecidable: an easy problem may reduce to a hard one. In fact that reverse reduction also exists here, but it is not the implication used in the proof.
Worked example 5.2.8
(Applying the reduction to concrete inputs)
Let halt on input and run forever on every other input. For the machine ignores its input and simulates , so it halts on : and . For , simulates and runs forever, so and . Both images are produced by the same mechanical wrapper, without running . Edge case: if is not a valid pair, is the code of the fixed looping machine, so and and the equivalence holds on malformed strings too.
is nevertheless recognizable: given a valid , simulate on and accept if it stops. A loop gives no negative answer, just as for . This observation does not produce a decider.
Exercises and solutions
Quick check
(A simulator has run for a million steps without stopping. Does this prove the simulated program never halts?)
Ask what a finite trace can and cannot rule out.
Solution · Answer
No. A program that stops after a million and one steps gives the same observation so far. A finite trace can prove a run has halted, but this observation alone cannot prove it will never halt.
Quick check
(In the diagonal proof, what happens if says halts on its own encoding?)
Check which branch of runs when answers yes.
Solution · Answer
The definition of makes it loop when says yes. Correctness of would simultaneously require that same run to halt, a contradiction. The no case gives the opposite contradiction, since then accepts and halts.
Quick check
(Given a machine and input , describe the empty-input machine used in the reduction. Does its construction decide whether halts on ?)
Is writing the wrapper's code the same as running it?
Solution · Answer
Generate a wrapper with and embedded. On any input it ignores that input and simulates . The wrapper's behavior on is therefore the behavior of . Generating its code is a finite syntactic operation; it does not run the simulation to completion or determine whether it halts.
Quick check
(If a problem reduces to an undecidable problem , does that alone show undecidable?)
Think of a trivially decidable and a map from it into a known undecidable language.
Solution · Answer
No. For example, the empty language reduces to any language with a computably constructible fixed nonmember, while the empty language is decidable. To prove a target undecidable using , start with a known undecidable and give a computable reduction .
Undecidability concerns the absence of a universal terminating procedure for the specified problem. Particular programs can still have short proofs of termination or nontermination; what fails is the promise of a correct finite answer for every encoded program and input.