Every programmer has written a program that "hangs": it runs and runs, and you cannot tell whether it is about to finish or stuck in an infinite loop forever. Wouldn't it be wonderful to have a tool that looks at any program and its input and simply tells you, "this will finish" or "this will loop forever"?
In 1936 Alan Turing proved that such a tool cannot exist. Not "nobody has built it yet", not "it would be too slow", but impossible, for every computer that will ever be built. This result, the undecidability of the halting problem, is the most famous theorem in the Theory of Computation and the starting point for almost every other undecidability result.
The halting problem asks: given (the description of) a Turing machine M and an input string w, does M halt on w? There is no Turing machine (no algorithm) that answers this question correctly for every pair (M, w). The halting problem is undecidable, although it is recursively enumerable (semi-decidable).
In this chapter we state the problem precisely, prove it undecidable step by step with the diagonal argument, do the same for the acceptance problem ATM, and see what follows for recursive and recursively enumerable languages. We build on Turing Machines and on the definitions in Decidability: Recursive & Recursively Enumerable Languages.
Why We Would Love a Halt Checker
Look at this small program. It repeatedly halves n if it is even, and replaces it by 3n + 1 if it is odd, until n becomes 1:
def collatz(n):
steps = 0
while n != 1:
n = n // 2 if n % 2 == 0 else 3 * n + 1
steps += 1
return steps
print(collatz(6), collatz(7), collatz(27)) # prints: 8 16 111For 6 it stops after 8 steps, for 7 after 16, and for 27 after 111 steps. Does this loop stop for every positive n? This is the Collatz conjecture, and nobody knows. It has been checked for an enormous range of numbers, but there is no proof.
Now imagine we had a perfect halt checker halts(program, input). We could write a program that searches n = 1, 2, 3, … and stops as soon as it finds an n for which collatz(n) does not halt, and ask halts whether that program halts. One call would settle a famous open problem. The same trick would settle many other open questions in mathematics (any statement of the form "there is no number with property P" where P can be checked mechanically). That should already make us suspicious that such a checker is too good to be true. Turing showed it is.
Stating the Problem Precisely
A Turing machine works on strings, so to give one machine to another as input we write it down as a string. Every TM M has an encoding ⟨M⟩ over a fixed alphabet (for example, binary): list its states, symbols and transitions in an agreed format. ⟨M, w⟩ denotes the encoding of the pair: the machine followed by its input, with a separator. This is exactly what a program file is: a string that describes a machine.
Two closely related languages are at the centre of this chapter:
Language | Definition | Question it captures |
|---|---|---|
HALTTM | { ⟨M, w⟩ : M is a TM and M halts on input w } | Does M stop (accepting or rejecting) on w? |
ATM (also written Lu, the universal language) | { ⟨M, w⟩ : M is a TM and M accepts w } | Does M accept w? |
Recall the three possible outcomes when a TM runs on an input: it accepts (halts in the accept state), it rejects (halts in the reject state, or halts without accepting), or it loops (never halts). "Halts" means accept or reject.
Saying "the halting problem is undecidable" means: the language HALTTM is not recursive. There is no TM that halts on every input ⟨M, w⟩ and accepts exactly those with M halting on w.
Halting Is Semi-Decidable
Before proving the negative result, notice the positive one. We can recognise halting: a universal Turing machine U takes ⟨M, w⟩ and simulates M on w step by step (just as an interpreter runs a program).
Recogniser R for HALT_TM, on input <M, w>:
1. Simulate M on w (using the universal TM).
2. If the simulation halts (accept or reject), ACCEPT.
M halts on w -> R eventually accepts (correct)
M loops on w -> R simulates forever (never says "no")So HALTTM is recursively enumerable. In the same way, ATM is recognised by "simulate M on w; accept if M accepts". The weakness is the "no" side: while the simulation is still running after a million steps, R cannot know whether M is about to stop or will run forever. A decider must always come back with an answer, and the proof below shows no amount of cleverness can fix this.
The Proof: Diagonalization
The proof is a proof by contradiction. The intuition: a perfect halt checker could be used to build a program that does the opposite of whatever the checker predicts about it. Then the checker must be wrong about that program.
Step 1: Assume a decider exists
Suppose, for contradiction, that some TM H decides HALTTM:
H(<M, w>) = ACCEPT if M halts on w
H(<M, w>) = REJECT if M does not halt on w
and H itself always halts.Step 2: Build the "contrary" machine D
Using H as a subroutine, build a new TM D that takes the description ⟨M⟩ of a machine and asks H what M does when fed its own description:
D, on input <M>:
1. Run H on <M, <M>>. (always finishes, since H is a decider)
2. If H says "M halts on <M>" -> go into an infinite loop.
If H says "M loops on <M>" -> halt.Feeding a machine its own description sounds odd, but it is perfectly legal: ⟨M⟩ is just a string, and every string is a valid input (think of running a compiler on its own source code). D is a real TM, because H is (by assumption) and the extra steps are easy.
Step 3: Run D on its own description
D is a TM, so it has an encoding ⟨D⟩. What happens when we run D on ⟨D⟩? D asks H about ⟨D, ⟨D⟩⟩, i.e. "does D halt on ⟨D⟩?"
Case | What H answers | What D then does | Conclusion |
|---|---|---|---|
D halts on ⟨D⟩ | "halts" | D loops forever | D does not halt on ⟨D⟩. Contradiction. |
D loops on ⟨D⟩ | "loops" | D halts | D does halt on ⟨D⟩. Contradiction. |
Either way we get a contradiction: D halts on ⟨D⟩ if and only if D does not halt on ⟨D⟩. The only assumption we made was that H exists. So H cannot exist.
Theorem (Turing, 1936). HALTTM is undecidable. No algorithm can decide, for every program and input, whether the program halts on that input.
Why it is called "diagonalization"
List all Turing machines M1, M2, M3, … (possible because each one is a finite string). Make a table whose entry in row i, column j says whether Mi halts (H) or loops (L) on input ⟨Mj⟩. The values below are just an illustration:
⟨M1⟩ | ⟨M2⟩ | ⟨M3⟩ | ⟨M4⟩ | … | |
|---|---|---|---|---|---|
M1 | H | L | H | H | … |
M2 | H | H | L | L | … |
M3 | L | L | L | H | … |
M4 | H | H | L | H | … |
D | L | L | H | L | ? |
D's behaviour on ⟨Mi⟩ is the opposite of the diagonal entry (Mi on ⟨Mi⟩). So D's row differs from row i in column i, for every i. D therefore differs from every machine in the list. But the list contains every TM, so if H existed, D would be in it, say D = Mk, and the entry at (k, k) would have to be both H and L. This is the same idea as Cantor's proof that the real numbers cannot be listed.
The same argument as code
Programmers often find this version the easiest to remember:
def halts(program_source, input_data):
... # suppose this always returns True/False correctly
def contrary(program_source):
if halts(program_source, program_source):
while True: # predicted to halt? then loop forever
pass
else:
return # predicted to loop? then stop at once
# Now call contrary(source_of_contrary).
# halts() says True -> contrary loops -> halts() was wrong.
# halts() says False -> contrary stops -> halts() was wrong.ATM Is Undecidable Too
The acceptance problem has exactly the same proof with "accept / reject" in place of "halt / loop".
Suppose H decides ATM: H(⟨M, w⟩) accepts if M accepts w, and rejects otherwise (M rejects or loops).
Build D: on input ⟨M⟩, run H on ⟨M, ⟨M⟩⟩ and output the opposite: if H accepts, D rejects; if H rejects, D accepts. D always halts.
Run D on ⟨D⟩. If D accepts ⟨D⟩, then H said "D does not accept ⟨D⟩", so D rejects. If D rejects ⟨D⟩, then H said "D accepts ⟨D⟩", so D accepts. Contradiction either way.
So ATM is undecidable (Sipser, Theorem 4.11). Since it is recognised by simulation, ATM is RE but not recursive.
The two problems are linked
We can also get one result from the other. Suppose HALTTM were decided by some H. Then this machine would decide ATM:
On input <M, w>:
1. Run H on <M, w>. If H says "M loops on w", REJECT.
2. Otherwise M is guaranteed to halt, so simulate M on w to the end
and ACCEPT if M accepted, REJECT if M rejected.Step 2 is safe because we only simulate when we know the simulation ends. Since ATM is undecidable, HALTTM must be undecidable too. This "if B were decidable, A would be decidable" pattern is called a reduction, and it is the main tool of the next chapter, Reductions & Rice's Theorem.
Consequences for Recursive and RE Languages
These results answer questions left open in Decidability: Recursive & Recursively Enumerable Languages.
1. Recursive ⊊ RE
ATM and HALTTM are RE but not recursive, so the recursive languages are a proper subset of the RE languages. There are problems a TM can confirm (when the answer is yes) but cannot decide.
2. The complements are not even RE
Recall the theorem: L is recursive if and only if both L and its complement are RE. (Run both recognisers in parallel, one step at a time; exactly one of them eventually accepts.)
Apply it to ATM. If the complement of ATM were RE, then ATM (which is RE) would be recursive, which we just proved false. Hence:
The complement of ATM, { ⟨M, w⟩ : M does not accept w }, is not recursively enumerable. Likewise the complement of HALTTM, { ⟨M, w⟩ : M does not halt on w }, is not RE.
Intuition: to confirm "M halts on w" you just wait until it halts. To confirm "M never halts on w" waiting never gives you certainty, and the theorem says no other method works for all machines.
3. Closure facts we can now prove
The RE languages are not closed under complement: ATM is RE, its complement is not. (The recursive languages are closed under complement: just swap accept and reject.)
Where the famous languages sit
Language | Recursive? | RE? | Complement RE? |
|---|---|---|---|
ATM = { ⟨M, w⟩ : M accepts w } | No | Yes | No |
HALTTM = { ⟨M, w⟩ : M halts on w } | No | Yes | No |
Complement of ATM | No | No | Yes |
Diagonal language Ld = { ⟨M⟩ : M does not accept ⟨M⟩ } | No | No | Yes |
ADFA, ACFG (does a DFA / CFG accept w?) | Yes | Yes | Yes |
So every language falls into one of three boxes: recursive (both it and its complement RE), RE but not recursive (like ATM), or not RE at all (like its complement, or Ld). A language and its complement can never be split as "one recursive, one RE-but-not-recursive".
What Is Decidable Nearby (Do Not Over-Apply the Theorem)
Undecidability of the halting problem is about general Turing machines, arbitrary inputs and unbounded running time. Change any of these and the problem may become decidable. Exams love this distinction.
Question | Decidable? | Why |
|---|---|---|
Does TM M halt on w within 1000 steps (or within k steps, k given)? | Yes | Simulate at most k steps, then answer. Always finishes. |
Does a DFA accept w? Does a CFG (or PDA) generate/accept w? | Yes | A DFA reads each symbol once and always stops; for a CFG (convert a PDA to a CFG first), the CYK algorithm decides membership. |
Does an LBA accept w? Does it halt on w? | Yes | With input length n there are at most |Q| · n · |Γ|n configurations. If the LBA runs longer than that, some configuration repeated, so it loops. Simulate up to that bound. |
Does a TM that never moves its head left halt on w? | Yes | After reading w it only ever sees blanks, so it behaves like a finite automaton; a repeated state on blank cells means looping. |
Does an arbitrary TM M halt on w? | No | The halting problem. |
Does M halt on the blank tape (empty input)? | No | Still undecidable; proved by reduction in the next chapter. |
A subtle point: one fixed machine
For one fixed pair (M0, w0), the question "does M0 halt on w0?" is technically decidable: the language is either {everything} or {nothing}, and both are decided by a trivial machine (one that always says yes, or one that always says no). We may not know which of the two is correct (think of the Collatz search program), but one of them is. Undecidability is a statement about a single algorithm that works for all inputs, not about one particular question.
Real computers have finite memory, so what?
A real computer with a fixed amount of memory is, strictly speaking, a huge finite-state machine, and its halting is decidable in principle (a repeated memory state means a loop). But with even 1 KB of memory there are 28192 states, so this observation is useless in practice. The TM model, with unbounded memory, describes the real situation much better: no general method is going to work.
Why It Matters in Practice
Perfect bug finders are impossible. "Will this program ever crash / divide by zero / dereference null / reach this line?" can be turned into a halting question, so no tool can answer it exactly for all programs. Real static analysers and compilers approximate: they are either sound but give false alarms, or precise but miss some cases, or time out.
Compiler optimisation: exact dead-code detection ("is this statement ever executed?") is undecidable, so compilers remove only code they can prove dead.
Malware detection: no program can decide for every program whether it will ever perform a malicious action, so antivirus tools rely on signatures and heuristics.
Termination checkers (in proof assistants like Coq/Rocq or Agda) accept only programs whose termination they can prove with simple rules, and reject some programs that do terminate.
Busy beavers: the maximum number of steps a halting n-state, 2-symbol TM can run (started on a blank tape) grows faster than any computable function. Only small values are known; in 2024 the bbchallenge collaboration completed a computer-verified proof that the 5-state value is 47,176,870 steps.
Common Mistakes
"The halting problem is not RE." Wrong. HALTTM is RE (simulate and wait); its complement is not RE.
"Undecidable means no TM accepts it." No: undecidable means no TM decides it (halts on all inputs with the right answer). An undecidable language can still be RE.
"We just need a faster computer or a smarter algorithm." The proof does not depend on speed; it rules out every algorithm, with any amount of time per input, as long as it always halts.
Saying "halting is undecidable for every TM". For many specific machines (or restricted classes, or bounded steps) halting is easy to decide. The claim is that no single algorithm works for all machines.
Getting D backwards. D does the opposite of H's prediction about M on ⟨M⟩: predicted halt → loop, predicted loop → halt. If D copied H's answer there would be no contradiction.
Forgetting that D must be a real TM. The contradiction only works because, if H existed, building D from it would be easy. That is why the conclusion is "H does not exist".
Confusing "loop" with "reject". A TM that rejects has halted. HALTTM contains ⟨M, w⟩ when M rejects w; ATM does not.
GATE and Interview Questions
Q1. Is the halting problem of Turing machines (a) recursive, (b) RE but not recursive, or (c) not RE?
(b) RE but not recursive. A universal TM recognises it by simulation; Turing's diagonal argument shows it cannot be decided.
Q2. Which of these is decidable? (i) Whether a TM halts on input w within 50 steps. (ii) Whether a TM halts on input w. (iii) Whether a DFA accepts w.
(i) and (iii) are decidable: (i) by simulating at most 50 steps, (iii) by running the DFA. (ii) is the halting problem, undecidable.
Q3. L is RE and its complement is also RE. What can you say about L?
L is recursive. Run the two recognisers alternately, one step each; one of them must eventually accept, and that tells us whether w ∈ L. This is why the complement of HALTTM cannot be RE.
Q4. In the proof, what does D do on input ⟨M⟩, and what is the contradiction?
D runs the hypothetical halt-decider H on ⟨M, ⟨M⟩⟩, loops if H says "halts" and halts if H says "loops". On input ⟨D⟩, D halts if and only if it does not halt, so H cannot exist.
Q5. Are the RE languages closed under complement? Justify.
No. ATM is RE, but its complement is not RE (otherwise ATM would be recursive).
Q6. Is acceptance decidable for linear bounded automata? Why does the halting proof not apply?
Yes, it is decidable. An LBA on input of length n has at most |Q| · n · |Γ|n distinct configurations, so after that many steps it must have repeated one and is looping. Simulating up to this bound always gives an answer. The diagonal proof needs a model whose memory is unbounded (a general TM).
Q7. Interview: your manager asks for a tool that flags every infinite loop in the codebase, with no false alarms and no misses. What do you say?
That exact tool is impossible: it would decide the halting problem. What we can build is an approximation, for example a linter that flags loops it can prove never terminate, a checker that proves termination for common patterns, or runtime timeouts, accepting some false positives or false negatives.
Q8. True or false: for the specific question "does program P0 halt on input 5?", there is a decider.
True. The answer is a fixed yes or no, and one of the two constant machines ("always accept" or "always reject") decides it. Undecidability needs infinitely many instances; it says no single algorithm answers all instances correctly.
Summary
HALTTM = { ⟨M, w⟩ : M halts on w } and ATM = { ⟨M, w⟩ : M accepts w } are both RE but not recursive.
They are RE because a universal TM can simulate M on w and report when it stops or accepts.
They are undecidable by diagonalization: from a supposed decider H build D that does the opposite of H's prediction about M on ⟨M⟩; D on ⟨D⟩ gives a contradiction.
A decider for HALTTM would give one for ATM, a first example of a reduction.
Their complements are not RE, so RE languages are not closed under complement, and recursive ⊊ RE.
Bounded versions (k steps, LBAs, DFAs, a single fixed instance) are decidable; the general problem is not.
In practice: no perfect loop detector, dead-code finder or virus scanner can exist, so real tools approximate.
A program that could predict any program's halting could be fed to a program that does the opposite of the prediction. That contradiction is the whole proof, and every later undecidability result is built on it.