Worked examples — Reducibility — many-one reductions

---

The scenario matrix

Every many-one reduction problem is really one of these cells. Below, each worked example is tagged with the cell it covers, so by the end every row is filled.

#	Cell (the case class)	What makes it tricky	Covered by
C1	Both directions checked (YES→YES and NO→NO)	forgetting the NO direction	Ex 1
C2	Decidability transfer ($B$ decidable ⇒ $A$ decidable)	using $f$ + a decider correctly	Ex 2
C3	Undecidability transfer ($A$ undecidable ⇒ $B$ undecidable)	picking the right known-hard $A$	Ex 3
C4	Degenerate targets: $B={\Sigma }^{\ast }$ (everything) or $B=\varnothing$ (nothing)	when does a reduction even exist?	Ex 4
C5	Complement flip ($A{\le }_{m}B\Rightarrow \overline{A}{\le }_m\overline{B}$)	same $f$, sets swapped	Ex 5
C6	Wrong-direction trap	reducing new→known proves nothing	Ex 6
C7	Recognizability (not decidability) transfer	$f$ where target-decider may loop	Ex 7
C8	Real-world word problem	translating an informal task into $f$	Ex 8
C9	Exam twist: build $f$ that is total even when it looks like it must simulate	avoid running $M$ inside $f$	Ex 9

---

Example 1 — both directions, a concrete finite reduction (C1)

Step 1. Define $f(w)=\{\begin{array}{ll}1& \text{if }w\text{ starts with }1,\\ 11& \text{otherwise.}\end{array}$ Why this step? We do not need $f$ to preserve $w$ at all — a many-one reduction only needs the YES/NO bit to survive. So we throw the input away and output a hand-picked string whose membership in $B$ matches membership in $A$. The string $1$ has odd length (in $B$); the string $11$ has even length (not in $B$).

Step 2. Check the YES direction. If $w$ starts with $1$ then $f(w)=1$, and $|1|=1$ is odd, so $f(w)\in B$. ✓ Why this step? This is $w\in A\Rightarrow f(w)\in B$ — the "useful" half.

Step 3. Check the NO direction. If $w$ does not start with $1$ (starts with $0$, or is empty) then $f(w)=11$, and $|11|=2$ is even, so $f(w)\notin B$. ✓ Why this step? This is the half everyone forgets. Without it a NO instance could sneak in as a YES image and the translator would lie — the reduction would wrongly accept a string not in $A$.

Step 4. Conclude $f$ is total and computable: read the first symbol, output $1$ or $11$. Always halts. Hence $A{\le }_{m}B$. Why this step? ${\le }_m$ is only earned once we confirm $f$ is a computable total function — the definition demands halting on every input, so we must explicitly certify termination before claiming the reduction exists.

Verify (explicit case table):

$w$	starts with 1? ($\in A$)	$f(w)$	$|f(w)|$ odd? ($\in B$)	agree?
$\text{101}$	yes	$1$	yes	✓
$\text{011}$	no	$11$	no	✓
$\epsilon$	no	$11$	no	✓
$\text{1111}$	yes	$1$	yes	✓
$\text{0}$	no	$11$	no	✓

All rows: $\in A$ column matches $\in B$ column. ✓

---

Example 2 — decidability transfer, used as a sanity check (C2)

Forecast: $B$ is trivially decidable ("does the string contain a 1?"). Will $f$ correctly turn "more 0s than 1s" into "contains a 1"?

Step 1. Compute $d={\#}_0(w)-{\#}_1(w)$ by one scan. Why this step? Counting is a guaranteed-terminating mechanical operation, so $f$ stays total — a looping $f$ would destroy decidability transfer, so we must keep every step of $f$ terminating.

Step 2. If $d>0$ output $0^{d}1$; else output $0$. Why this step? We want the presence of a 1 in the output to track "$A$ says YES". When $d>0$ we append a $1$; when $d\le 0$ we output the single symbol $0$ (no $1$ anywhere).

Step 3. Both directions:

• $w\in A$ ($d>0$) $\Rightarrow f(w)=0^{d}1$ contains a $1$ $\Rightarrow f(w)\in B$. ✓
• $w\notin A$ ($d\le 0$) $\Rightarrow f(w)=0$ contains no $1$ $\Rightarrow f(w)\notin B$. ✓

Step 4. Apply Theorem 1 (decidability transfer): $B$ decidable, $A{\le }_{m}B$, so decide $A$ by "compute $f(w)$, then check if it contains a $1$." Since $A$ is obviously decidable directly, this is a sanity check that the machinery is sound. Why this step? This is the payoff of the whole reduction: Theorem 1 lets us reuse $B$'s decider through $f$, so establishing $A{\le }_{m}B$ was the point — the conclusion is not automatic until we invoke the transfer theorem by name. See also Turing-recognizable vs Decidable languages.

Verify (explicit case table):

$w$	$d={\#}_0-{\#}_1$	more 0s? ($\in A$)	$f(w)$	has a 1? ($\in B$)	agree?
$\text{000}$	$3$	yes	$\text{0001}$	yes	✓
$\text{0011}$	$0$	no	$\text{0}$	no	✓
$\text{01}$	$0$	no	$\text{0}$	no	✓
$\text{00011}$	$1$	yes	$\text{01}$	yes	✓
$\text{111}$	$-3$	no	$\text{0}$	no	✓

All rows agree. ✓

---

Example 3 — undecidability transfer (C3): the direction that does real work

Figure — what you are looking at. The board shows the machine $M_w$ that the reduction writes down, split into its only two possible fates. Top box (chalk-blue): the case $M$ accepts $w$. Because $M_w$ erases its own input $x$ and just runs $M$ on $w$, once $M$ accepts $w$ the machine $M_w$ accepts no matter what $x$ was — so it "leaks" acceptance to every input and $L(M_w)={\Sigma }^{\ast }$, which is non-empty. The blue arrow (labelled $f$) carries this to the right column: $⟨M_w⟩\notin E_{TM}$. Bottom box (chalk-pink): the case $M$ does not accept $w$. Then the inner simulation never accepts, so $M_w$ accepts nothing, $L(M_w)=\varnothing$, and the pink arrow carries it to $⟨M_w⟩\in E_{TM}$. The single design — "ignore $x$, run $M$ on $w$" — is exactly what makes $M_w$'s language all-or-nothing: it is either every string or no string, and which of the two it is exactly mirrors whether $M$ accepts $w$. That all-or-nothing property is the whole trick.

Step 1. Given $⟨M,w⟩$, build the description of a new machine $M_w$: "On any input $x$: erase $x$, run $M$ on $w$; if $M$ accepts $w$, accept." Why this step? $M_w$'s behaviour no longer depends on $x$ (top vs bottom box in the figure). So its language is either all strings (if $M$ accepts $w$) or empty (if $M$ does not) — never anything in between.

Step 2. Set $f(⟨M,w⟩)=⟨M_w⟩$. Why this step? $f$ only writes down the code of $M_w$; it never runs $M$. Pure text editing ⇒ $f$ is total and computable (running $M$ inside $f$ could loop and would make $f$ partial — see Ex 9).

Step 3. Check the biconditional against $\overline{A_{TM}}$ (the "$M$ does not accept $w$" language; recall $⟨M,w⟩\in \overline{A_{TM}}$ means exactly $⟨M,w⟩\notin A_{TM}$):

• $⟨M,w⟩\in \overline{A_{TM}}$ ($M$ does not accept $w$) $\Rightarrow L(M_w)=\varnothing \Rightarrow ⟨M_w⟩\in E_{TM}$. ✓ (pink path)
• $⟨M,w⟩\notin \overline{A_{TM}}$ ($M$ accepts $w$) $\Rightarrow L(M_w)={\Sigma }^{\ast }\ne \varnothing \Rightarrow ⟨M_w⟩\notin E_{TM}$. ✓ (blue path)

Step 4. Apply Theorem 2 (undecidability transfer): so $\overline{A_{TM}}{\le }_m{E}_{TM}$, and since $\overline{A_{TM}}$ is undecidable (complement of an undecidable language is undecidable), $E_{TM}$ is undecidable. Hardness flowed along the arrow into $E_{TM}$. Why this step? Theorem 2 (contrapositive of decidability transfer) is what actually concludes the proof: a valid ${\le }_m$ from a known-hard language forces the target hard. Without naming this theorem, Steps 1–3 are just a function — the undecidability result is only earned here.

Recall Why reduce

$\overline{A_{TM}}$ and not $A_{TM}$? Because our $f$ maps "accepts" to "non-empty" — the YES side of $A_{TM}$ lands on the NO side of $E_{TM}$. Flipping to $\overline{A_{TM}}$ realigns YES with YES. (You could equally state it as $A_{TM}{\le }_m\overline{E_{TM}}$.) Compare Rice's Theorem, which gives this for free.

Verify (explicit two-world table):

world	$⟨M,w⟩\in \overline{A_{TM}}$?	$L(M_w)$	$⟨M_w⟩\in E_{TM}$?	agree?
$M$ accepts $w$	no	${\Sigma }^{\ast }$	no	✓
$M$ does not accept $w$	yes	$\varnothing$	yes	✓

Both worlds: source membership matches target membership. ✓

---

Example 4 — degenerate targets ${\Sigma }^{\ast }$ and $\varnothing$ (C4)

Step 1. Take $B={\Sigma }^{\ast }$. We need $f$ with $w\in A⟺f(w)\in {\Sigma }^{\ast }$. But $f(w)\in {\Sigma }^{\ast }$ is always true. So the biconditional forces $w\in A$ to always be true, i.e. $A={\Sigma }^{\ast }$. Why this step? The right side of the biconditional is a constant; a biconditional with a constant right side forces the left side constant too.

Step 2. So $A{\le }_m{\Sigma }^{\ast }$ holds iff $A={\Sigma }^{\ast }$. Symmetrically $A{\le }_m\varnothing$ holds iff $A=\varnothing$ (since $f(w)\in \varnothing$ is always false, forcing $A=\varnothing$). Why this step? We must cover the nothing language too — the same constant-side argument runs with "false" instead of "true", so both degenerate targets are pinned down.

Step 3. The other direction: what reduces from a trivial $A$? If $A={\Sigma }^{\ast }$, pick any fixed $b\in B$ and set $f(w)=b$ (constant). Then $w\in A$ (always) $⟺f(w)=b\in B$ (true) — valid provided $B\ne \varnothing$. If $B=\varnothing$ there's no such $b$, so ${\Sigma }^{\ast }/{\le }_m\varnothing$, matching Step 2. Why this step? Constant functions are the simplest totals; checking when they work isolates the only obstruction (an empty target has no image to hit).

Step 4. The four trivial-target cases, spelled out:

$A$	$B$	does $A{\le }_{m}B$ exist?	reason
${\Sigma }^{\ast }$	${\Sigma }^{\ast }$	yes	$f(w)=$ any fixed member of ${\Sigma }^{\ast }$
${\Sigma }^{\ast }$	$\varnothing$	no	${\Sigma }^{\ast }$ has a YES string but $\varnothing$ has no member to send it to
$\varnothing$	${\Sigma }^{\ast }$	yes	$f(w)=$ any fixed non-member... none exist, but every $w\notin \varnothing$ so map anywhere; biconditional is "false $⟺$ true"? no — see note
$\varnothing$	$\varnothing$	yes	$f(w)=$ any fixed non-member of $\varnothing$ (every string)

Careful reading of row 3: $A=\varnothing$ means every $w$ is a NO instance, so we need $f(w)\notin {\Sigma }^{\ast }$ for all $w$ — impossible, since everything is in ${\Sigma }^{\ast }$. So $\varnothing /{\le }_m{\Sigma }^{\ast }$. Corrected: $A=\varnothing$ reduces only to targets that miss at least... in fact $\varnothing {\le }_{m}B$ iff $B\ne {\Sigma }^{\ast }$ (we need a non-member to hit). The clean rule is below.

Verify (explicit truth check): treat each language as a pair (has-a-member?, has-a-nonmember?). ${\Sigma }^{\ast }=(\text{yes},\text{no})$, $\varnothing =(\text{no},\text{yes})$. Then ${\Sigma }^{\ast }{\le }_{m}B$ needs $B$ to have a member; $\varnothing {\le }_{m}B$ needs $B$ to have a non-member. Checked below.

---

Example 5 — the complement flip (C5)

Step 1. Recall $w\in A⟺f(w)\in B$. Negate both sides: $w\notin A⟺f(w)\notin B$, i.e. (using the complement definition $w\in \overline{L}\iff w\notin L$) $w\in \overline{A}⟺f(w)\in \overline{B}$. Why this step? A biconditional $P⟺Q$ is logically identical to $\neg P⟺\neg Q$. No new function needed — the same translator works on the complemented sets.

Step 2. Verify concretely. $w=\text{011}\in \overline{A}$ (doesn't start with 1); $f=11$, $|11|=2$ even, so $f\in \overline{B}$. ✓ And $w=\text{1}\notin \overline{A}$; $f=1$, odd, $f\notin \overline{B}$. ✓ Why this step? A single algebraic negation can hide a slip; plugging in a YES and a NO instance confirms the complemented reduction really holds.

Step 3. Why we care: this is the engine for non-recognizability proofs. If $A{\le }_{m}B$ and $A$ is not Turing-recognizable, then neither is $B$ (Theorem 4); complementing lets you carry results about $\overline{A_{TM}}$ around (see Turing-recognizable vs Decidable languages and Closure properties of language classes).

Verify (explicit case table, same $f$, complemented sets):

$w$	$\in \overline{A}$? (not start 1)	$f(w)$	$\in \overline{B}$? ($|f|$ even)	agree?
$\text{011}$	yes	$11$	yes	✓
$\text{1}$	no	$1$	no	✓
$\epsilon$	yes	$11$	yes	✓
$\text{101}$	no	$1$	no	✓

All rows agree. ✓

---

Example 6 — the wrong-direction trap (C6)

Step 1. State the transfer theorem precisely: Theorem 2 says $A{\le }_{m}B$ and $A$ undecidable $\Rightarrow$ $B$ undecidable. The hardness lands on the right end of ${\le }_m$. Why this step? We must pin down which side inherits hardness before judging the argument.

Step 2. The student's reduction is $HAL{T}_{TM}{\le }_m{A}_{TM}$. Matching this to Theorem 2, the "$A$" is $HAL{T}_{TM}$ and the "$B$" is $A_{TM}$. Theorem 2 would let us conclude something about the right side ($A_{TM}$) — which we already knew is undecidable. It says nothing about the left side $HAL{T}_{TM}$. Why this step? "Hardness flows along the arrow" — into the head, not the tail; matching the roles to the theorem exposes that the wanted conclusion is about the tail, which the theorem never constrains.

Step 3. The correct argument reverses the arrow: $A_{TM}{\le }_{m}HAL{T}_{TM}$ (the parent's Example 1: build $M^{\prime }$ that runs $M$ on $w$, accepts if $M$ accepts and loops if $M$ rejects). Now, matching Theorem 2, "$A$" = the known-hard $A_{TM}$ and "$B$" = the target $HAL{T}_{TM}$, so undecidability flows into $HAL{T}_{TM}$. Conclusion earned. ✓ Why this step? Fixing the direction re-aligns the known-hard language with the tail and the target with the head, which is the only configuration Theorem 2 lets us conclude from.

Verify (logic check): the inference "$A{\le }_{m}B$ and $A$ undecidable $\Rightarrow$ $B$ undecidable" is valid; the inference "$B{\le }_{m}A$ and $A$ undecidable $\Rightarrow$ $B$ undecidable" is not valid (a decidable $B$ can reduce to an undecidable $A$). Checked below.

---

Example 7 — recognizability, not decidability, transfer (C7)

Step 1. Let $R_B$ recognize $B$: it accepts every $x\in B$, but on $x\notin B$ it may reject or loop forever (this is the definition of recognizer given at the top). Why this step? "Recognizable" is the weaker guarantee — halting only promised on YES instances, so we must track where looping can occur.

Step 2. Build $R_A$: on input $w$, compute $x=f(w)$ (halts, $f$ total), then run $R_B$ on $x$; accept if $R_B$ accepts. Why this step? $f$ total ⇒ the first stage always finishes; the loop risk lives only inside $R_B$, so we have located the single source of non-halting.

Step 3. Correctness: $R_A$ accepts $w⟺R_B$ accepts $f(w)⟺f(w)\in B⟺w\in A$. So $R_A$ accepts exactly the strings of $A$. Why this step? This chain is the reduction property threaded through the recognizer; it certifies that the set $R_A$ accepts is precisely $A$, which is what "recognizes $A$" means.

Step 4. But when $w\notin A$, we have $f(w)\notin B$, and $R_B$ may loop — so $R_A$ may loop on those inputs. It never wrongly accepts, but it need not halt-and-reject. That is exactly a recognizer, not a decider. This is Theorem 3. Why this step? It explains the gap: the halting guarantee we lost in $B$ we cannot recover in $A$, so decidability transfer downgrades to recognizability transfer.

Step 5. Contrapositive (Theorem 4): if $A$ is not recognizable, then $B$ is not recognizable — the standard tool for the "$\overline{A_{TM}}$ is not recognizable" family. Why this step? Flipping Theorem 3 gives the workhorse used to prove languages outside the recognizable class; it is the recognizability twin of Example 3's undecidability transfer. Connects to Decidability and the Halting Problem.

Verify (acceptance identity): on YES instances the accept-condition chain $R_A\text{ acc}⟺R_B\text{ acc}(f(w))⟺w\in A$ is a logical identity; it never accepts a NO instance. Checked below.

---

Example 8 — a real-world word problem (C8)

Step 1. Represent each config $c$ as a Turing machine $M_c$ that, on any input, simulates the config's rule engine and emits the name of a triggered step whenever the config would fire one. Why this step? We translate the informal predicate "triggers a step" into the formal "produces output," aligning $L$ with $D$ so a ${\le }_m$ can even be stated.

Step 2. Set $f(c)=⟨M_c⟩$. This is text editing over the config, so $f$ is total and computable. Why this step? We never run the config inside $f$ (that could loop); we only compile it — same discipline as Example 3 and 9, which keeps $f$ total as ${\le }_m$ demands.

Step 3. Both directions:

• $c\in L$ (no step ever triggers) $\Rightarrow M_c$ never outputs $\Rightarrow ⟨M_c⟩\in D$. ✓
• $c\notin L$ (some step can trigger) $\Rightarrow M_c$ can output $\Rightarrow ⟨M_c⟩\notin D$. ✓ Why this step? Both directions confirm the YES/NO bit survives, so the translation is a genuine reduction and not a one-sided illusion.

Step 4. Apply Theorem 2 (undecidability transfer): $L{\le }_{m}D$ and $D{\le }_{m}L$ symmetrically, so the two are equivalent; since the underlying emptiness question is undecidable (Example 3's $E_{TM}$), no perfect linter exists. Why this step? The practical verdict ("no decider possible") is only licensed by Theorem 2 applied to the equivalence with $E_{TM}$ — the reduction is the bridge, the transfer theorem is the conclusion. The engineering takeaway: ship a sound over-approximation (a recognizer), never claim a decider.

Verify (explicit two-world table):

world	triggers a step?	$c\in L$?	$M_c$ outputs?	$⟨M_c⟩\in D$?	agree?
never triggers	no	yes	no	yes	✓
can trigger	yes	no	yes	no	✓

Both worlds: $\in L$ matches $\in D$. ✓

---

Example 9 — the exam twist: keep $f$ total (C9)

Step 1. Consider the case $M$ loops on $w$ (neither accepts nor rejects). Then $f$'s "run $M$ on $w$" step never halts, so $f(⟨M,w⟩)$ is undefined. Why this step? $⟨M,w⟩$ with looping $M$ is a genuine NO instance of $A_{TM}$ we are obligated to map somewhere. If $f$ diverges there, $f$ is partial, not total — illegal.

Step 2. So the proposed $f$ is not a valid ${\le }_m$ reduction. The fix is to build $f$ by editing $M$'s description (as in Ex 3 and Ex 8): output the code of a machine that will do the simulation later, so $f$ itself always halts. Why this step? Delaying the simulation to run-time of the output machine keeps $f$ total while preserving the YES/NO correspondence — the definition of ${\le }_m$ is only met by a total $f$.

Step 3. General rule of thumb for exams: $f$ may compile but must not execute the machine it is reasoning about. Compilation halts; execution may not.

Recall One-line diagnosis test

Ask: "On the hardest NO instance — a looping $M$ — does my $f$ still halt?" If not, $f$ is partial and the reduction is invalid.

Verify (logic check): "run $M$ then branch" is total $⟺M$ halts on all inputs, which is not guaranteed for $A_{TM}$; the code-editing version is unconditionally total. Checked below.

---

Scenario matrix — filled

Recall Did we cover every cell?

Which example handles the "$B={\Sigma }^{\ast }$ / $B=\varnothing$" degenerate case? ::: Example 4. Which example is the one where hardness must flow into the target? ::: Examples 3 and 6. Which example shows a recognizer arises when the target-decider may loop? ::: Example 7. Which example fails only because $f$ becomes partial on a looping machine? ::: Example 9. Which example uses the same $f$ on complemented sets? ::: Example 5. Which example translates an informal engineering task into a reduction? ::: Example 8.

Related: Polynomial-time reductions and NP-completeness adds a time bound to the exact same $f$-discipline you drilled here.