Questions: Undecidable Problems and the Halting Problem

Question 1

A computer scientist proposes that the halting problem might become solvable as quantum processors become exponentially faster and AI improves dramatically. This proposal is:

• A. Plausible — the halting problem is currently unsolvable due to processing speed and memory constraints
• B. Incorrect — undecidability is a mathematical theorem about the logical structure of computation, not a hardware or resource limitation
• C. Correct — quantum computing operates on different principles and may circumvent classical undecidability results
• D. Requires further research — current theory doesn't account for AI-based approaches to theorem proving

Answer: (B)

Undecidability is not an engineering problem waiting for a better computer. It is a mathematical impossibility proved by contradiction: if a halting decider existed, the diagonalization argument produces a machine that contradicts itself — a logical impossibility that no increase in speed, memory, or computational paradigm can resolve. Quantum computers still operate within the Turing model (they solve the same class of decidable problems, just faster for some), and AI does not escape formal computability limits.

Question 2

In the diagonalization proof, machine D runs the assumed halting decider H on the input (M, M) — a machine given its own description. Why is this self-referential step essential?

• A. It reduces the computational cost of the proof by reusing the same input twice
• B. Self-reference creates the logical contradiction that forces H's non-existence — D's behavior on its own description leads to 'D halts iff D does not halt'
• C. It is an arbitrary notational convention chosen for compactness; any two inputs would produce the same result
• D. It ensures the proof applies only to Turing machines that process their own source code

Answer: (B)

Self-reference is the entire engine of the proof. When D is run on its own description, H must return 'yes' or 'no' — but either answer forces D to behave in the opposite way, directly contradicting H's output. If H says 'D halts on D,' then D is constructed to loop. If H says 'D loops on D,' then D halts. There is no consistent answer — H's supposed correctness is refuted by the very machine it's applied to. Without self-reference, this contradiction cannot be constructed.

Question 3

The halting problem is currently unsolvable but will likely become solvable as computing hardware and software advance sufficiently.

• T. True
• F. False

Answer: False

Undecidability is a mathematical theorem, not a technological limitation. The proof shows that assuming a halting decider exists leads to a logical contradiction — which means no such decider can exist, regardless of how powerful the hardware becomes. This is not like a problem that is computationally hard (like factoring large numbers) but theoretically solvable; it is a formal impossibility. No amount of processing power, memory, or new programming technique can resolve a logical contradiction.

Question 4

The diagonalization proof shows that if a halting decider H existed, it would give an incorrect answer when presented with a specially constructed machine D — proving H cannot exist.

• T. True
• F. False

Answer: True

This is precisely what the proof demonstrates. Machine D is constructed so that it does the opposite of what H predicts: if H says 'D halts on D,' D loops; if H says 'D does not halt on D,' D halts. Either way, H is wrong about D's behavior on its own input (D, D). Since H was assumed to be correct for all inputs, this contradiction shows H cannot exist — there is no Turing machine that correctly decides the halting problem for all inputs.

Question 5

Explain in your own words why the diagonalization proof of the halting problem's undecidability works. What makes the self-reference essential, and what contradiction does it produce?

Model answer: The proof assumes for contradiction that a machine H exists that correctly decides, for any machine M and input w, whether M halts on w. Using H, we build machine D: given a machine description M as input, D asks H whether M halts on M (its own description). If H says yes, D deliberately loops; if H says no, D halts. Now run D on its own description. If D halts, then H must have said 'no' about D — but H is supposed to be correct, meaning D should not halt. Contradiction. If D loops, then H must have said 'yes' — but that means D should halt. Contradiction again. H gives the wrong answer in either case, so H cannot exist. Self-reference is essential because only by asking about a machine's behavior on its own description can we construct a machine whose existence directly refutes H's correctness — any other input pairing doesn't close the loop.

The diagonalization technique originates in Cantor's proof that real numbers are uncountable and Gödel's incompleteness theorems. In each case, self-reference constructs a statement or object that cannot consistently be classified by the system claiming to classify everything. The halting problem proof is a direct instance of this general logical pattern: self-reference + assumed completeness = unavoidable contradiction.