A student constructs a computable function f such that for any (M, w), f(M, w) = ⟨M'⟩ where M' accepts all inputs iff M halts on w. She claims this proves L_total = {⟨M⟩ : M halts on every input} is undecidable. Why does her construction succeed?
ABecause f is computable, any problem reducible from it must be decidable
BBecause if L_total were decidable, composing a decider for L_total with f would decide HALT, contradicting HALT's undecidability
CBecause f reduces L_total to HALT, showing L_total is no harder than HALT
DBecause M' accepts all inputs, proving totality is a trivial property
This is the reduction proof by contrapositive. f defines HALT ≤_m L_total. Suppose L_total were decidable by machine D. Given any (M, w), compute f(M, w) = ⟨M'⟩, then run D on ⟨M'⟩. D accepts iff M' ∈ L_total iff M' halts on every input iff M halts on w — so D∘f decides HALT. Since HALT is undecidable, this contradiction shows L_total must be undecidable too. Option C confuses the direction: f reduces *from* HALT *to* L_total, establishing that L_total is at least as hard as HALT, not the other way.
Question 2 Multiple Choice
A researcher shows that language A ≤_m language B, and B is known to be decidable. What can be concluded about A?
AA is undecidable — the reduction shows A is at least as hard as B
BA is decidable — the reduction function combined with a decider for B decides A
CNothing — many-one reductions do not preserve decidability
DA is decidable only if the reduction function is injective
When A ≤_m B via computable f and B has a decider D_B, we decide A as follows: on input x, compute f(x) and run D_B on f(x); accept iff D_B accepts, since x ∈ A iff f(x) ∈ B. Reductions carry decidability downward (from B to A). The contrapositive — used in undecidability proofs — is: if A is undecidable and A ≤_m B, then B must be undecidable. Option C is wrong; reducibility does preserve both decidability and undecidability in the appropriate directions.
Question 3 True / False
To prove L is undecidable via reduction from HALT, the reduction function f must satisfy: (M, w) ∈ HALT if and only if f(M, w) ∈ L.
TTrue
FFalse
Answer: True
This biconditional is the exact requirement for a many-one reduction HALT ≤_m L. Both directions are necessary: the ⟹ direction (if M halts on w, then f(M, w) ∈ L) and the ⟸ direction (if f(M, w) ∈ L, then M halts on w). Together they guarantee that a hypothetical decider for L, composed with f, would correctly decide HALT. A one-directional implication is insufficient — it would allow L-instances to behave differently from HALT-instances in the missing direction, breaking the simulation.
Question 4 True / False
Showing that HALT ≤_m L (HALT reduces to L) proves that HALT is undecidable, since L's undecidability transfers back to HALT.
TTrue
FFalse
Answer: False
This reverses both the direction and the logic. HALT ≤_m L means L is at least as hard as HALT — L's undecidability flows *from* HALT's, not toward it. HALT's undecidability is the *premise* (established independently by the diagonal argument), not the conclusion. The proof shows: if L were decidable, HALT would be decidable — contradiction — so L is undecidable. You cannot use a reduction to prove HALT undecidable; reductions propagate hardness *to* the target language, not back to the source.
Question 5 Short Answer
Why does the direction of a many-one reduction matter when proving undecidability? What goes wrong if the reduction runs in the wrong direction?
Think about your answer, then reveal below.
Model answer: To prove L undecidable, you need HALT ≤_m L — a computable f transforming HALT instances into L instances. This shows that solving L would solve HALT (impossible), so L has no decider. If you construct L ≤_m HALT instead, you've only shown that HALT is at least as hard as L — already known, since HALT is undecidable. The wrong direction tells you nothing about L's decidability: L might still be decidable by some means that doesn't go through HALT. The reduction must flow from the known-hard problem to the target to propagate hardness to the target.
Intuition: 'A ≤_m B' means 'B is at least as hard as A — a B-solver can simulate an A-solver.' For undecidability, you want to show your target (L) is hard enough to simulate HALT. That requires HALT ≤_m L. The reverse (L ≤_m HALT) only shows HALT is hard enough to simulate L — but HALT's hardness was already established. The direction of the reduction is the direction of hardness inheritance.