Questions: The Halting Problem

Question 1

Turing's proof that the halting problem is undecidable establishes that:

• A. No computer can determine whether any specific program halts on a given input
• B. Modern computers lack the memory to simulate all programs
• C. No single algorithm can correctly decide, for every program-input pair, whether the program halts
• D. Programs that loop forever cannot be detected before they run

Answer: (C)

The proof does not say anything about individual programs — we can often tell whether a specific program halts. It says that no general-purpose halting detector exists: there is no algorithm H such that H(P, x) correctly answers 'halts' or 'loops' for every possible program P and input x. This is an absolute mathematical limitation, not a practical one about speed or memory.

Question 2

The undecidability of the halting problem means that for most program P, it is extremely difficult to determine whether P halts on any given input.

• T. True
• F. False

Answer: False

Undecidability is a claim about the non-existence of a *general* algorithm — one that works correctly for all programs and inputs. For many specific programs, halting behavior is easily determined (e.g., a program with no loops trivially halts). The proof shows there is no single algorithm covering all cases, not that every individual case is mysterious.

Question 3

In the diagonalization proof, why does the machine D — defined to do the opposite of what H predicts for D on itself — create a contradiction?

Model answer: D is constructed so that if H predicts D halts on input D, then D actually loops; and if H predicts D loops, D halts. In either case H's prediction is wrong. Since D is a legitimate program and D itself is a valid input, this means H fails on the specific pair (D, D), contradicting the assumption that H correctly decides halting for all inputs.

This is the diagonalization trick borrowed from Cantor: construct an object that necessarily disagrees with any proposed complete description. D's self-referential behavior is not a curiosity — it is a precise, constructive proof that H cannot exist. Any proposed halting oracle can be defeated by the D built from it.