Questions: Many-One Reducibility in Computability

Question 1

You prove that A_TM (the TM acceptance problem) many-one reduces to language L, i.e., A_TM ≤_m L. Given that A_TM is undecidable, what can you conclude about L?

• A. L is decidable, because the reduction provides an efficient translation between A_TM and L instances
• B. L is undecidable, because a decider for L would give us a decider for A_TM via the reduction
• C. Nothing can be concluded about L; the reduction only tells us about A_TM's relationship to L
• D. L is undecidable only if L also reduces many-one back to A_TM

Answer: (B)

The key transfer property: if A ≤_m B and A is undecidable, then B must be undecidable. Proof by contrapositive — if L were decidable, compose the reduction function f with L's decider to decide A_TM. Since A_TM is not decidable, neither can L be. Option 2 is the most tempting wrong answer: it suggests the reduction is uninformative, but the *direction* A_TM ≤_m L (A_TM maps into L) is precisely what propagates undecidability upward to L. Only if the reduction went the other way (L ≤_m A_TM) would we learn nothing new about L.

Question 2

In the many-one reduction A ≤_m B via function f, what does f do?

• A. f decides membership in A by using an oracle for B as a subroutine
• B. f transforms instances of A into instances of B such that membership is preserved in both directions
• C. f transforms instances of B into instances of A, allowing A to be solved using B's structure
• D. f accepts strings in A and rejects strings not in A, using the same steps a B-decider would use

Answer: (B)

The reduction function f maps from A to B: it takes any string w (an instance of A) and produces f(w) (an instance of B) satisfying w ∈ A iff f(w) ∈ B. This is a one-way translation that preserves the yes/no membership answer. Option 2 reverses the direction — it describes B ≤_m A, which is a different and unrelated reduction. Option 0 confuses many-one reducibility with Turing reducibility (oracle computation). The function f is purely a translator; it does not decide A on its own.

Question 3

The reduction function f in A ≤_m B must be total — it must halt and produce output for every input string w, including strings not in A.

• T. True
• F. False

Answer: True

Totality is not optional. The composition argument works like this: to decide whether w ∈ A, compute f(w) (which must halt), then run the B-decider on f(w). If f were partial and looped on some inputs, the composed procedure would also loop, breaking the decidability transfer. Crucially, f must produce output for strings *not in A* as well — for those, f(w) must be a string *not in B*, and f must reach this output in finite time. The mapping is defined for the entire domain Σ*, not just strings in A.

Question 4

If A ≤_m B and B is undecidable, then A should also be undecidable.

• T. True
• F. False

Answer: False

This is a common inversion of the correct rule. A ≤_m B says A is no harder than B — if B were decidable, A would be too. B being *undecidable* does not pull A up to undecidability. A could be a trivially decidable language (say, the empty language ∅, which a TM can decide by always rejecting) that reduces many-one to an undecidable B via a constant function mapping everything to a string not in B. The useful direction is: if A ≤_m B and *A* is undecidable, then B is undecidable. B's hardness does not constrain A's hardness.

Question 5

Explain why the reduction function f must output a *description* of a machine M' rather than running M on w, even though the reduction's correctness depends entirely on M's behavior on w.

Model answer: If f ran M on w, f would loop forever on any input where M does not halt — making f partial (undefined for those inputs) and breaking the composition. Instead, f performs only string manipulation: it takes ⟨M, w⟩ as input and outputs a description of a new machine M' that *encodes* contingent behavior ('simulate M on w; if M halts, do X'). Constructing this description is always a finite mechanical operation — f is essentially writing a short program as a string, without executing it. The description of M' is always a finite string producible in bounded time, even if running M' would be infinite.

The 'describe but don't run' pattern is the fundamental technique in computability theory for constructing things that depend on undecidable behavior. It exploits the fact that a Turing machine is just a data structure — a finite description of a computation. You can manipulate, compose, and embed TM descriptions as strings without ever executing them. The constructed M' may run forever when invoked, but its description is always a finite string. Once you internalize this pattern, most undecidability proofs follow a standard template: receive ⟨M, w⟩, construct M' by text manipulation, map to the target language's format.