A software company wants to build a static analyzer that, before deploying any program, checks whether the program contains an infinite loop. According to the halting problem, this tool:
ACould be built with sufficiently advanced AI, but current computers are too slow
BCan be built but will occasionally give wrong answers — no perfect tool is possible
CCannot be built as a general solution for all programs — not because it's hard, but because it's theoretically impossible
DCan be built for most practical programs, just not for Turing-complete ones
The halting problem proves that no algorithm — not even a hypothetical one running on a perfect computer with infinite time — can decide for all programs and all inputs whether the program halts. This is not a limitation of current hardware or AI; it is a mathematical impossibility. A practical static analyzer can flag many specific cases (e.g., loops with no exit condition), but it will necessarily either fail to catch some infinite loops or produce false positives on non-looping programs. Option B comes close, but the correct framing is 'impossible in general,' not merely 'occasionally wrong.'
Question 2 Multiple Choice
The proof that the halting problem is undecidable works by constructing a machine D that does the opposite of what the assumed halting decider H predicts. Why does D being given its own description as input create a contradiction?
ABecause D's description is too long for any Turing machine to read
BBecause D(⟨D⟩) either halts (contradicting H's prediction it loops) or loops (contradicting H's prediction it halts) — no consistent answer exists
CBecause a Turing machine cannot accept its own description as input
DBecause D's behavior is random, making H's prediction meaningless
The self-referential construction is the heart of the diagonalization. If H predicts D(⟨D⟩) halts, then D (by construction) loops — contradicting H. If H predicts D(⟨D⟩) loops, then D halts — again contradicting H. Every possible output of H leads to a contradiction. The contradiction is not about size or randomness; it arises from a logically airtight self-referential loop. This is directly analogous to Cantor's diagonalization, which constructed a real number differing from every number on a proposed list.
Question 3 True / False
The halting problem is undecidable because modern computers lack the processing power to analyze most possible programs. Future quantum computers may eventually solve it.
TTrue
FFalse
Answer: False
This is the most common misconception about undecidability. Undecidability is not a statement about computational resources — it is a statement about the logical limits of any algorithm, on any computer, with any amount of time and memory. The proof does not assume any hardware limitations; it works for any Turing machine, which is the theoretical model capturing 'everything computable.' Quantum computers cannot solve undecidable problems; they extend what is efficiently solvable, not what is algorithmically solvable in principle.
Question 4 True / False
The halting problem (HALT_TM) is recognizable: you can run the machine M on input w and accept if it halts. This makes HALT_TM recognizable but not decidable.
TTrue
FFalse
Answer: True
Recognizability only requires that you accept if the answer is 'yes' — you never need to reject or detect 'no.' Running M on w and accepting when it halts works perfectly: if M halts, you eventually accept. The problem is the 'no' case: if M loops forever, your simulation also loops forever — you cannot distinguish looping from a very long computation. Decidability requires always halting with the correct answer (accept or reject). HALT_TM is recognizable but not decidable because there is no algorithm that detects the infinite-loop case.
Question 5 Short Answer
Explain why the diagonalization argument for the halting problem leads to a contradiction. What is the role of the self-referential machine D?
Think about your answer, then reveal below.
Model answer: Assume a decider H exists for the halting problem. Construct D: on input ⟨M⟩, D runs H(⟨M, ⟨M⟩⟩) and does the opposite — halts if H says M loops, loops if H says M halts. Now feed D its own description: D(⟨D⟩). If H correctly predicts D halts, then D loops (contradiction). If H correctly predicts D loops, then D halts (contradiction). H cannot give a correct answer, so no such H can exist.
The power of D is that it weaponizes H's correctness against itself. Any answer H gives for the pair (D, ⟨D⟩) is immediately falsified by D's behavior. The construction is deterministic — D's behavior is fully defined relative to H's output — so this isn't a paradox of self-reference but a rigorous proof by contradiction. The analogy to Cantor's diagonalization is precise: just as Cantor constructed a real number differing from every row of a proposed list, Turing constructed a computation differing from every row of H's output table.