Exercises — Reducibility — many-one reductions

Forward (YES $\to$ YES): every string $w$ that is in $A$ must map to a string $f(w)$ that is in $B$. Backward (NO $\to$ NO): every string $w$ that is not in $A$ must map to a string $f(w)$ that is not in $B$. Equivalently the backward direction is the contrapositive: if $f(w)\in B$ then $w\in A$. Checking only the first line is the classic broken "reduction".

(a) NO — $f$ must be total (halt on every input). A looping $f$ breaks the decidability transfer. (b) YES — identity is computable and total; it witnesses $A{\le }_{m}A$ (reflexivity). (c) YES — reductions are literally called many-one: $f$ may collapse many inputs to one output. It need not be injective or onto.

False. Read ${\le }_m$ literally as "$\le$": $A{\le }_{m}B$ says $A$ is no harder than $B$ — i.e. $B$ is at least as hard as $A$. Hardness flows along the arrow, from $A$ into $B$.

Define $f(w)=\{\begin{array}{ll}w1& \text{if }w\text{ contains a }1\\ w0& \text{if }w\text{ contains no }1\end{array}$. This is computable (scan $w$ once, then append one bit) and total.

• $w\in A$ (has a 1) $\Rightarrow f(w)$ ends in $1\Rightarrow f(w)\in B$. ✓
• $w\notin A$ (all zeros / empty) $\Rightarrow f(w)$ ends in $0\Rightarrow f(w)\notin B$. ✓ Both directions hold, so $A{\le }_{m}B$. (Sanity: appending the marker bit forces the target predicate "ends in 1" to mirror the source predicate "has a 1".)

$A=\{w:|w|\text{ is even}\}$.

• $|\epsilon |=0$ (even) $\Rightarrow f(\epsilon )=\text{0}$, which ends in 0 $\Rightarrow \in B$. ✓ (and $\epsilon \in A$).
• $|\text{01}|=2$ (even) $\Rightarrow f(\text{01})=\text{010}$, ends in 0 $\Rightarrow \in B$. ✓
• $|\text{1}|=1$ (odd) $\Rightarrow f(\text{1})=\text{11}$, ends in 1 $\Rightarrow \notin B$. ✓ (and $\text{1}\notin A$).

Let $M_B$ decide $B$. Define $M_A$ on input $w$:

1. Compute $x=f(w)$. (Halts: $f$ is total & computable.)
2. Run $M_B$ on $x$. (Halts: $M_B$ is a decider.)
3. Accept if $M_B$ accepts $x$; reject if $M_B$ rejects $x$. Both steps always halt $\Rightarrow M_A$ always halts. Correctness: $M_A$ accepts $w⟺M_B$ accepts $f(w)⟺f(w)\in B⟺w\in A$. So $M_A$ decides $A$.

This is the contrapositive of Theorem 1 ("$A{\le }_{m}B$ and $B$ decidable $\Rightarrow A$ decidable"). Suppose for contradiction $B$ were decidable. Since $A{\le }_{m}B$, Theorem 1 gives $A$ decidable. But we are given $A$ undecidable — contradiction. Hence $B$ is undecidable. $■$ The reduction arrow points from the known-hard $A$ into the target $B$.

Start from the reduction property: for all $w$, $w\in A⟺f(w)\in B.$ Negate both sides of the biconditional (a biconditional is preserved under negating both sides): $w\notin A⟺f(w)\notin B.$ Rewrite membership in complements: $w\in \overline{A}⟺f(w)\in \overline{B}.$ That is exactly the statement $\overline{A}{\le }_m\overline{B}$ via the same total computable $f$. The reverse direction is identical by symmetry ($\overline{\overline{A}}=A$). $■$ (See Closure properties of language classes for why this is the go-to move in non-recognizability proofs.)

The claim reduces $B$ into the known-hard problem, i.e. it shows $B$ is no harder than $A_{TM}$ — which is almost every recognizable language, telling us nothing about $B$'s hardness. To prove $B$ undecidable you need $A_{TM}{\le }_{m}B$ (arrow from the hard problem into $B$). Direction reversed $\Rightarrow$ conclusion unjustified. In fact $B$ could be trivially decidable and still satisfy $B{\le }_m{A}_{TM}$.

Reduction $f$: on input $⟨M,w⟩$, output $⟨M^{\prime },w⟩$ where $M^{\prime }$ is $M$ edited so that: run $M$ on $w$; if $M$ accepts, $M^{\prime }$ accepts (halts); if $M$ rejects, $M^{\prime }$ enters an infinite loop. (Purely mechanical editing of $M$'s description — no simulation performed by $f$ itself, so $f$ is total & computable.)

• $⟨M,w⟩\in A_{TM}$ ($M$ accepts) $\Rightarrow M^{\prime }$ halts $\Rightarrow ⟨M^{\prime },w⟩\in HAL{T}_{TM}$. ✓
• $⟨M,w⟩\notin A_{TM}$ ($M$ rejects or loops) $\Rightarrow M^{\prime }$ loops $\Rightarrow ⟨M^{\prime },w⟩\notin HAL{T}_{TM}$. ✓ Both directions hold, so $A_{TM}{\le }_{m}HAL{T}_{TM}$; since $A_{TM}$ is undecidable, so is $HAL{T}_{TM}$.

By Exercise 4.1 we have $A_{TM}{\le }_{m}HAL{T}_{TM}$ via some total computable $f$. By the complement lemma (Exercise 3.2) the same $f$ gives $\overline{A_{TM}}{\le }_m\overline{HAL{T}_{TM}}$. What it buys you: $\overline{A_{TM}}$ is a known not-Turing-recognizable language. By the recognizability transfer (Theorem 4: $A$ not recognizable and $A{\le }_{m}B\Rightarrow B$ not recognizable), $\overline{HAL{T}_{TM}}$ is not Turing-recognizable either.

Use the composition $h(w)=g(f(w))$.

• Computable & total: running $f$ halts (total) and produces $f(w)$; then running $g$ on $f(w)$ halts (total). Sequencing two always-halting machines always halts, so $h$ is total computable.
• Correctness chain: $w\in A⟺f(w)\in B⟺g(f(w))\in C⟺h(w)\in C.$ Hence $A{\le }_{m}C$ via $h=g\circ f$. $■$

Take $A=\{w:|w|\text{ even}\}$, $B=\{w:w\text{ ends in }0\}$, $f(w)=w0$ if $|w|$ even else $w1$ (from the parent note). Both directions verified there; both languages are decidable. No contradiction: a reduction is neutral machinery. $A{\le }_{m}B$ only says "$A$ is no harder than $B$." When both are easy, that statement is simply true and unhelpful for hardness. Reductions prove hardness only when you plug a known-hard $A$ into the arrow (Theorem 2). Here neither side is hard, so it is merely a consistency check.

• Forward: $w\in A\Rightarrow f(w)=w\in {\Sigma }^{\ast }=B$. ✓ (everything is in $B$).
• Backward: need $w\notin A\Rightarrow f(w)\notin B$. But $B={\Sigma }^{\ast }$, so $f(w)\in B$ always, including for non-palindromes. So a NO-instance of $A$ maps to a YES-instance of $B$. ✗ Verdict: NOT a valid reduction. You cannot reduce anything nontrivial to the trivial language ${\Sigma }^{\ast }$ (or to $\varnothing$), because a constant-truth target cannot mirror a source that has both YES and NO instances. This is the biconditional biting back.

Which known-hard $A$? $A_{TM}$ (or its complement). Direction: $A_{TM}{\le }_m\overline{L}$ (map $⟨M,w⟩$ to a machine $M^{\prime }$ whose language is nonempty exactly when $M$ accepts $w$). By Theorem 2, $\overline{L}$ undecidable $\Rightarrow L$ undecidable (decidability is closed under complement). Cross-check: $L(M)=\varnothing$ is a nontrivial semantic property of the recognized language (some machines have it, some don't; it depends only on $L(M)$). Rice's Theorem then instantly gives undecidability — the reduction above is exactly the engine behind Rice's Theorem.

Direction for hardness proofs ::: reduce known-hard $A$ into target $B$: $A_{undec}{\le }_{m}B$. Both directions of a reduction ::: $w\in A\Rightarrow f(w)\in B$ and $w\notin A\Rightarrow f(w)\notin B$. Requirement on $f$ ::: total + computable (always halts, no simulation-loop). Complement lemma ::: $A{\le }_{m}B⟺\overline{A}{\le }_m\overline{B}$ via the same $f$. Why you can't reduce to ${\Sigma }^{\ast }$ or $\varnothing$ ::: a constant-truth/false target can't mirror the NO/YES direction.