From a slogan to a precise machine
In the previous guide a reduction was a slogan and a translator: 'if I could solve B, I could solve A,' so A's hardness rubs off on B. That intuition is right, but a slogan does not transfer impossibility — a careful definition does. The cleanest one is the mapping reduction (also called a many-one reduction). It demands not a clever back-and-forth conversation between the two problems, but one honest, fixed translation done up front, computed by a machine that always halts.
Here is the definition in words. A language A mapping-reduces to a language B (written A <=m B) if there is a total computable function f — a Turing machine that halts on every input — such that for every string w, w is in A if and only if f(w) is in B. The phrase 'if and only if' is doing all the heavy lifting: f must send yes-instances of A to yes-instances of B, AND no-instances to no-instances. It is a faithful translator of membership, never a liar in either direction. Notice f does not have to decide anything; it only rewrites the question.
Why the translator transfers decidability
The whole point of the definition is one short chain of reasoning. Suppose A <=m B via f, and suppose — for a happy moment — that B were decidable, with a decider D_B that always halts with yes or no. Then we could build a decider for A out of spare parts: given w, first run f to translate it into f(w), then hand f(w) to D_B and echo its answer. Because f always halts and D_B always halts, the combined machine always halts. And because w is in A exactly when f(w) is in B, the echoed answer is correct. So A would be decidable too.
Now flip that into its contrapositive, which is the form you will actually use. If A is known to be UNdecidable and A <=m B, then B must be undecidable too — because if B had a decider, the construction above would hand us a decider for A, contradicting that A has none. This is exactly the transfer of undecidability, and it is also where the direction from guide 1 becomes life-or-death. You point the arrow FROM the known-hard A TO your new target B. Reduce halting to B, never B to halting. Get the arrow backwards and you have proved only that your easy problem is no harder than a hard one — a true but useless statement.
KNOWN HARD YOUR TARGET
A = A_TM --------- f ---------> B = ???
(undecidable) mapping (you want to show undecidable)
Build a decider for A out of: [ translate w into f(w) ] --> [ decider for B ] --> echo answer
If B had a decider ==> A would too ==> contradiction ==> B has no decider.
Arrow rule: reduce the KNOWN-hard problem TO your new one (A <=m B).
Backwards (B <=m A) proves nothing about B's hardness.It also carries the weaker promise: recognizability
A mapping reduction is generous: the very same translator transfers more than decidability. It also moves recognizability — the weaker promise of a machine that says yes on every yes-instance but may loop forever on a no-instance. Re-run the argument with a recognizer instead of a decider: given w, compute f(w) and feed it to a recognizer for B. If w is in A then f(w) is in B and the recognizer accepts; if w is not in A then f(w) is not in B and the recognizer either rejects or loops — which is exactly the behaviour a recognizer for A is allowed to have. So if B is recognizable and A <=m B, then A is recognizable.
Take the contrapositive again and you get the sharpest tool of all: transferring unrecognizability. If A is known to be UNrecognizable and A <=m B, then B is unrecognizable. The standard way to wield this is a small twist. From guide 1's neighborhood you know the complement of the universal acceptance language, the language NOT-A_TM, is unrecognizable. A handy fact about mapping reductions seals the deal: A <=m B holds if and only if (complement of A) <=m (complement of B), because the same f works for both — it respects the biconditional whichever side you call 'yes'. So to prove some B is unrecognizable, you often reduce A_TM to the complement of B; that is the same as reducing NOT-A_TM to B, and the unrecognizability rides across.
A gallery of fallen problems
With one engine and one source of hardness you can topple a whole row of dominoes. Take Turing-machine emptiness — does a given machine M accept no strings at all, is its language empty? Reduce A_TM to it: given (M, w), build a new machine M' that ignores its own input, simulates M on the fixed w, and accepts only if M accepts w. Then M' accepts everything (a non-empty language) when M accepts w, and accepts nothing (the empty language) when M does not. So deciding emptiness of M' would decide whether M accepts w — but that is A_TM, which is undecidable. Emptiness falls. The function that builds M' from (M, w) is plainly total and computable, so it is a legitimate mapping reduction.
From emptiness, equivalence of two Turing machines (do M_1 and M_2 recognize the same language?) topples almost for free: emptiness is just the special case 'is M equivalent to a machine that rejects everything?', so a decider for equivalence would decide emptiness. The same contagion reaches further than machines. The Post correspondence problem — a puzzle about lining up dominoes so the top and bottom strings match — is undecidable by a (more intricate) reduction from the halting problem, encoding a machine's computation history as a domino-matching game. And once PCP has fallen, it becomes the hammer that kills several grammar problems: whether a context-free grammar is ambiguous, and whether two context-free grammars generate the same language. The next two guides in this rung tell those two stories in full.
Loosening the rules: Turing reductions and oracles
A mapping reduction is a strict, one-shot translator: rewrite the question once, ask B once, report B's answer unchanged. Sometimes that is too rigid. The looser notion is a Turing reduction, built on an oracle machine — an ordinary Turing machine handed one superpower: a magic consultant, the oracle for problem B, which instantly answers any yes/no membership question about B. A Turing reduction says: A is solvable by a machine that may consult the B-oracle as many times as it likes, in any pattern, and may freely combine, negate, or branch on the answers before deciding A. Think of B as a subroutine you may call repeatedly, not a translation you do once.
This freedom buys real power. Every mapping reduction is a Turing reduction (call the oracle once, echo it), but not the reverse. The clean example: a language and its complement are always Turing-equivalent — with an oracle for B you decide the complement of B by asking the oracle and flipping the answer. Yet a language can fail to mapping-reduce to its own complement (that is exactly how A_TM and NOT-A_TM differ in recognizability). So Turing reductions are strictly more flexible. The honest cost of that flexibility: a Turing reduction transfers decidability faithfully — if B is decidable and A Turing-reduces to B, then A is decidable — but it does NOT preserve recognizability, because it may ask the oracle about no-instances and act on the 'no', a move a plain recognizer cannot make. For undecidability proofs alone, Turing reductions are enough and often easier; for the finer unrecognizability results, you must stay with mapping reductions.
The recursion theorem: a machine that knows itself
One loose end has been nagging since the halting-problem proof. That proof built a machine that asks about its own description and then does the opposite — but is it really legal for a machine to get hold of its own code? The recursion theorem says yes, cleanly and in full generality: any Turing machine can, as part of its operation, obtain its own complete description and compute with it. The mind-bending part is there is no infinite regress, no machine that must contain a copy of a machine that contains a copy of itself forever. A finite machine can refer to its own (finite) code. The everyday cousin you have already met is the quine — a program that prints its own source with no input and without reading its file.
The recursion theorem is two things at once. As a RESULT it tames self-reference: self-reference is not paradoxical or forbidden in computation; it is an ordinary, available capability. As a PROOF TOOL it is a gift, because it lets you write proofs that say 'let M be a machine that, using its own description, does the following...' without any circular hand-waving. For example, you can prove A_TM undecidable in one stroke: suppose a halting-decider H existed; build a machine R that obtains its own description angle-bracket R angle-bracket, asks H whether R halts on its input, and then does the opposite of H's prediction. R contradicts H on its own behaviour, so H cannot exist. That is the diagonalization self-reference of the halting proof, now licensed and made routine by the recursion theorem.
- Decide direction first: to show your target B is hard, set A to a problem ALREADY proved hard (A_TM, the halting problem, or anything downstream of them) and aim for A <=m B — never B <=m A.
- Design a total computable f mapping each instance of A to an instance of B, so that yes-instances go to yes-instances and no-instances go to no-instances (the biconditional).
- Verify BOTH directions of the biconditional by tracing the yes-case and the no-case, and confirm f always halts. A leak in either direction voids the reduction.
- Conclude by contrapositive: since A is undecidable (or unrecognizable) and A <=m B, B inherits that same impossibility. If you only need undecidability, a Turing reduction (with an oracle, possibly queried many times) also works.