Reducibility — many-one reductions: Visual walkthrough

Step 1 — Draw the two worlds

WHAT. Picture two big boxes side by side. The left box is the world of all strings — every possible string you could type. Inside it, a shaded blob is $A$ : the strings that are "in $A$ " (the YES-strings). Everything outside the blob but still inside the box is $\overline{A}$ (the NO-strings). The right box is the same idea for language $B$ .

WHY. A "language" sounds abstract. But a language is nothing more than a chosen set of YES-strings sitting inside the sea of all strings. Deciding the language means: given a dot, is it inside the blob or outside? Drawing it this way turns an abstract set-membership question into a pointing-at-a-region question.

PICTURE. Left: box with blob $A$ . Right: box with blob $B$ . No connection yet — that comes next.

Figure — Reducibility — many-one reductions

Step 2 — The translator $f$ is an arrow-drawing machine

WHAT. Now draw arrows from each dot in the left box to a dot in the right box. Every left-dot gets exactly one arrow out. That collection of arrows is the function $f$ : it takes a string $w$ (left) and produces a string $f (w)$ (right).

WHY THIS TOOL, a function and not something fancier? We want a mechanical, reliable translator: give it a question about $A$ , it hands back a question about $B$ . "Reliable" means two things a plain function guarantees:

Everybody gets an arrow (the function is total — defined on every input). No string is left hanging.
Each string gets exactly one arrow (it is a function, not a random guess). Same input → same output, every time.

We do not demand the arrows be one-to-one. Several left-dots may land on the same right-dot — that is literally why it's called many-one. We also don't demand every right-dot is hit. A plain function is the weakest tool that still lets us pipe questions across — so it's the right tool.

PICTURE. Several arrows from the left box to the right box; two different left-dots share one arrowhead on the right (showing "many-to-one" is allowed).

Step 3 — The one rule the arrows must obey

WHAT. Not any arrows will do. We demand: every arrow that starts inside blob $A$ must land inside blob $B$ , and every arrow that starts outside $A$ must land outside $B$ . In symbols, for every string $w$ : $start inside A w \in A ⟺ land inside B f (w) \in B .$

Reading each piece:

$w \in A$ — "the dot $w$ sits inside the left blob."
$f (w) \in B$ — "the arrowhead lands inside the right blob."
$⟺$ — "these two facts are the same fact": one is true exactly when the other is.

WHY. This biconditional is the whole contract. It says the translator never lies: a YES-question always becomes a YES-question, a NO-question always becomes a NO-question. That double promise is what will let us borrow $B$ 's answers.

PICTURE. Colour-coded arrows: green (inside→inside) allowed, and a red forbidden arrow crossing from inside $A$ to outside $B$ struck out — that broken arrow is the trap of "only checking the YES direction."

Step 4 — Chain the pipes: build a decider for $A$ out of a decider for $B$

WHAT. Suppose someone hands us $M_{B}$ , a machine that decides $B$ (always halts, says YES/NO correctly). We now assemble a machine $M_{A}$ for $A$ by wiring two boxes in a row:

Feed $w$ into $f$ . Out comes $x = f (w)$ . (Step-2 machine — always halts, because $f$ is total.)
Feed $x$ into $M_{B}$ . (The given decider — always halts.)
Echo $M_{B}$ 's answer as $M_{A}$ 's answer.

WHY. We are recycling a solved problem. We never invented a fresh idea for $A$ ; we translated the $A$ -question into a $B$ -question and reused the $B$ -machine. That is the entire spirit of a reduction.

PICTURE. A pipeline: input $w$ → box $f$ → wire carrying $x = f (w)$ → box $M_{B}$ → answer, with a dashed outer box labelled " $M_{A}$ " wrapping both.

Step 5 — Why $M_{A}$ always halts (the totality step)

WHAT. Being correct isn't enough for a decider; it must also always answer — never loop forever. Walk the pipeline and check each box halts:

Box $f$ : halts on every input — that's what "total" bought us in Step 2.
Box $M_{B}$ : halts on every input — that's what "decider" means.

Two boxes that always halt, wired in series, still always halt.

WHY. This is exactly where the "make $f$ total" rule earns its keep. If $f$ could loop on some $w$ , the pipeline would hang at box 1, and $M_{A}$ would fail to be a decider — it would only be a recognizer. That single missing property is the difference between " $A$ is decidable" and " $A$ is merely recognizable."

PICTURE. The same pipeline with a green "always halts" stamp on each box, and a struck-out red version where a partial $f$ loops (a curled arrow going nowhere) and the whole pipeline hangs.

Step 6 — Flip the picture: hardness flows along the arrow

WHAT. Take Theorem 1 — " $A \leq_{m} B$ and $B$ decidable $\Rightarrow$ $A$ decidable" — and read it backwards (its contrapositive). If $A$ is undecidable, then $B$ cannot be decidable. Same arrow, opposite reading: $(A \leq_{m} B \land A undecidable) \Rightarrow B undecidable. (Theorem 2)$

WHY. Logic: " $P \Rightarrow Q$ " is identical to "not $Q \Rightarrow$ not $P$ ." Here $P$ = " $B$ decidable", $Q$ = " $A$ decidable". If $A$ is not decidable (not $Q$ ), then $B$ is not decidable (not $P$ ). Nothing new is assumed — it's the same theorem wearing a different hat.

PICTURE. The arrow $A \to B$ with a big amber "HARDNESS" flowing from $A$ into $B$ . Underneath, the reversed (wrong) arrow $B \to A$ crossed out with the note "tells you nothing about $B$ ."

Step 7 — Degenerate cases, so nothing surprises you

WHAT & WHY (four corner cases). Push the machine to its edges and confirm it still behaves.

$A = \emptyset$ (empty blob). No string is in $A$ , so the contract $w \in A ⟺ f (w) \in B$ becomes " $false ⟺ f (w) \in B$ ", i.e. $f$ must send every string outside $B$ . As long as $B \neq = Σ^{*}$ , pick any fixed string $b_{0} \in / B$ and set $f (w) = b_{0}$ . Empty language reduces to anything non-full.
$A = Σ^{*}$ (full box). Every string is in $A$ ; the contract needs $f (w) \in B$ always. Pick a fixed $b_{1} \in B$ (needs $B \neq = \emptyset$ ) and set $f (w) = b_{1}$ .
$f$ constant. A constant $f$ is a perfectly good "many-one" map (maximally many-to-one!). It works iff the constant lands on the correct side for every $w$ — which only happens when $A$ is $\emptyset$ or $Σ^{*}$ . That's why cases 1–2 used constants and general $A$ cannot.
Reflexive edge: $A \leq_{m} A$ . Let $f (w) = w$ (identity — trivially computable and total). The arrows go straight across; contract $w \in A ⟺ w \in A$ is automatic. Every language is no harder than itself.

PICTURE. Four mini-panels: empty blob → constant arrow to a NO-dot; full box → constant arrow to a YES-dot; a fan of arrows collapsing to one point (constant); and identity arrows going straight across.

The one-picture summary

WHAT. One diagram compresses all seven steps: the left blob $A$ , the right blob $B$ , the total function $f$ carrying inside→inside and outside→outside, and the wired pipeline $w \to f \to M_{B} \to$ answer that is the decider $M_{A}$ . The amber "hardness" arrow reminds us which way Theorem 2 flows.

Recall Feynman retelling — say it like you're explaining to a friend

Picture two islands of "YES-strings," $A$ and $B$ . A reduction is a reliable postal service $f$ : hand it any letter (string) about island $A$ , it always delivers exactly one letter to island $B$ — and it never misfiles. YES-letters land in $B$ 's YES-pile, NO-letters land in $B$ 's NO-pile. That single honesty rule ( $w \in A ⟺ f (w) \in B$ ) is the heart of everything.

Now suppose $B$ has a perfect oracle that answers any $B$ -question and always finishes. To answer a question about $A$ , I just mail it through $f$ to $B$ , ask $B$ 's oracle, and echo the reply. Because the postal service never misfiles and never gets lost (it's total), my answer for $A$ is always right and always arrives. So: $B$ solvable ⟹ $A$ solvable.

Read that backwards and you get the real workhorse: if I already know $A$ is unsolvable, then $B$ can't be solvable either — otherwise I'd have just solved $A$ . Hardness rides the arrow from the known-hard tail into the new head. That one sentence powers nearly every undecidability proof you'll meet, from $H A L T_{T M}$ to Rice's Theorem, and the same skeleton with a running clock gives you Polynomial-time reductions and NP-completeness.

Recall Quick self-test

The arrow $A \leq_{m} B$ makes which one at least as hard? ::: $B$ (the arrowhead / right side). Why must $f$ be total, not partial? ::: So the pipeline never hangs; totality is what upgrades "recognizer" to "decider." Both directions of $w \in A ⟺ f (w) \in B$ mean what pictorially? ::: inside→inside AND outside→outside (both arrow colours). To prove new $B$ undecidable, reduce which way? ::: known-hard $A \leq_{m} B$ (arrow into $B$ ).