Questions: Reduction Techniques for Proving Undecidability

Question 1

You want to prove that L = {⟨M⟩ : M accepts at least one string} is undecidable. You build a computable function f where f(⟨M, w⟩) = ⟨M'⟩, and M' is defined to accept all strings if M accepts w, and accept nothing otherwise. What does this prove?

• A. It reduces L to the halting problem, proving the halting problem is undecidable relative to L
• B. It reduces the halting problem to L (H_TM ≤_m L), proving L is undecidable
• C. It reduces L to itself, which is circular and proves nothing
• D. It proves L is decidable by showing it can simulate the halting problem

Answer: (B)

The function f maps halting-problem instances ⟨M, w⟩ to L-instances ⟨M'⟩, establishing H_TM ≤_m L. The iff holds: if M accepts w (⟨M,w⟩ ∈ H_TM), then M' accepts all strings, so ⟨M'⟩ ∈ L; if M does not accept w, M' accepts nothing, so ⟨M'⟩ ∉ L. Since H_TM is undecidable and H_TM ≤_m L, a decider for L would give a decider for H_TM — contradiction. The reduction arrow always points from the known-hard problem toward the problem you want to prove hard. Option 0 reverses the direction and proves nothing new.

Question 2

When constructing the reduction function f for H_TM ≤_m L, you need to build a new machine M' from the input ⟨M, w⟩. Which of the following correctly describes what f does?

• A. f runs M on w, and if M halts, outputs a description of M' that accepts some strings
• B. f outputs a description of M' as a string — encoding what M' would do — without executing M on w
• C. f calls a subroutine that decides L on the input ⟨M, w⟩ and builds M' based on the result
• D. f enumerates strings until it finds one that M accepts, then constructs M' to accept that string

Answer: (B)

The reduction function must be total and computable — it must halt and produce output for every input. Option 0 fails because running M on w may loop forever, making f non-total and breaking the composition argument. Options 2 and 3 either beg the question (using an L-oracle) or are non-halting (enumeration may not terminate). The correct approach is purely mechanical: f examines ⟨M, w⟩ as strings and constructs a description of M' by writing a program that says 'simulate M on w, then behave accordingly.' This description is always a finite string producible in finite time.

Question 3

In a many-one reduction from A to B, the reduction function f must be both total (halt on every input) and computable (implementable by a Turing machine).

• T. True
• F. False

Answer: True

Both conditions are essential to the composition argument. Totality ensures f(x) always terminates, so the composed procedure 'compute f(x), then run B's decider on f(x)' always terminates. If f were partial (looping on some inputs), the composition might loop even when a B-decider exists, breaking the decidability transfer. Computability ensures f can actually be implemented. A reduction using a non-computable function would be useless as a proof technique — you would need an oracle to compute f in the first place.

Question 4

To prove that language L is undecidable, the correct strategy is to reduce L to the halting problem — that is, construct a reduction L ≤_m H_TM.

• T. True
• F. False

Answer: False

This gets the direction backwards. Reducing L to H_TM (L ≤_m H_TM) shows only that L is no harder than H_TM — it says that if you could decide H_TM, you could decide L. Since H_TM is already known to be undecidable, this tells you nothing about L's decidability. To prove L undecidable, you reduce the halting problem *to* L (H_TM ≤_m L): show that a decider for L would enable deciding H_TM. The arrow must point FROM the known-undecidable problem TO the new one you want to prove hard.

Question 5

Explain why the reduction function f cannot simply run M on w when constructing the reduced machine M', even though M's behavior on w is what the reduction depends on.

Model answer: If f ran M on w, f would loop forever on any input where M does not halt — making f a partial function. A partial f breaks the composition: a hypothetical L-decider calling f(⟨M,w⟩) would loop before reaching the decision step, so the composed 'decider' for H_TM would not actually decide. Instead, f constructs a description of M' as a finite string — writing code that says 'simulate M on w, then behave accordingly' — without executing that code. Constructing a description is always finite and mechanical, even when running the described computation would be infinite.

The key insight is the distinction between *describing* a computation and *running* it. You can always write 'while(true){}' in a moment, even though executing it never terminates. Similarly, f writes the description of M' (a finite string) immediately from ⟨M,w⟩ using string manipulation, never invoking a TM simulator. The M' description encodes contingent behavior ('if M halts on w, do X'), which is representable in finite text. This 'describe but don't run' pattern is the core technique underlying virtually all undecidability proofs.