Picking up the thread: from one impossible problem to many
By the end of the last rung you owned a small but precious collection of impossibilities. The halting problem — given a machine and an input, will it eventually halt or loop forever? — has NO algorithm that always answers correctly, and we cornered that fact with a diagonalization argument that fed a machine its own description. We also met its close cousin, the acceptance problem A_TM (does this machine accept this input?), shown undecidable the same way. These results are airtight but lonely: each one was proved by hand. The natural next thought is, do we have to redo that delicate diagonalization for every new problem we suspect is impossible?
Happily, no. There is a reusable lever, and it is the engine of this whole rung. A reduction is, in one phrase, a translator that turns one problem into another. If I can translate every question about problem A into an equivalent question about problem B — so that solving B would automatically solve A — then A is no harder than B. Flip that statement around and you get the version we will exploit relentlessly: if A is already known to be impossible, then B must be impossible too, because a solver for B would hand us a solver for A. One stubborn impossibility, the halting problem, can now infect every problem we can reduce it to.
Which way does the arrow point?
Here is the rule, stated so you can tattoo it on the inside of your eyelids. To prove that YOUR new problem B is undecidable, you reduce a KNOWN-undecidable problem A TO B. We write this 'A reduces to B', or 'A <= B', read as 'A is no harder than B'. The known-hard thing sits on the LEFT, your suspected-hard target on the RIGHT. The arrow flows FROM the established impossibility INTO the new problem you want to condemn. This is the whole of reduction direction, and almost every undecidability proof you will ever write is an instance of it.
Why does the direction matter so violently? Because 'A <= B' carries impossibility ONE WAY only. It says a solver for B yields a solver for A, so 'B is solvable' would force 'A is solvable'. We contrapose that — flip it via the contrapositive you met in the foundations — into 'A is NOT solvable, therefore B is NOT solvable'. The hardness of A flows downhill into B. It does NOT flow the other way: knowing your problem B is hard tells you nothing about A, and reducing your problem TO the halting problem proves nothing about your problem. That backwards reduction is real and sometimes even true, it is just useless as a hardness proof.
A vivid sanity check fixes the direction forever. You want to prove your problem B is hard. You imagine, for contradiction, a magic solver for B. Now YOU, the proof-writer, are the one who must build a solver for the famous hard problem A — using B's magic solver as a subroutine. So you write a translator that takes any instance of A, turns it into an instance of B, runs the magic B-solver, and reads off the answer to A. If that translator exists, then a B-solver would defeat the halting problem, which is impossible; so the B-solver cannot exist. Notice the labour: YOU translate FROM A INTO B. You are always trying to attack the known-impossible problem with the new problem's hypothetical power.
Two flavours of reduction: mapping and Turing
Not all translators are equally clean, and there are two flavours worth distinguishing now. The tidiest is the mapping reduction (also called a many-one reduction). It is a single computable function f that rewrites each input w into a new input f(w), with one ironclad promise: w is a yes-instance of A exactly when f(w) is a yes-instance of B. No peeking at the answer, no second call — you translate ONCE, ask B's solver ONCE, and B's verdict on f(w) IS the verdict on w. Because the yes/no matching is exact, a mapping reduction from A to B transfers not only undecidability but also unrecognizability, a finer transfer the next guide leans on.
The roomier flavour is the Turing reduction, built on a charming fiction called an oracle machine. Picture an ordinary Turing machine — your endless rewritable notebook — but it owns a magic telephone. At any moment it can write a question on a special tape and, in a single step, hear back a perfect yes/no answer to some fixed problem B. That phone-answerer is the oracle. A Turing reduction from A to B is then any oracle machine that decides A while making calls to a B-oracle — and crucially it may call MANY times, use earlier answers to decide what to ask next, and even flip the oracle's reply. It is the most permissive sense of 'if I could solve B, I could solve A'.
Why keep both? Mapping reductions are strict — one call, answers matched on the nose — and that strictness is exactly what lets them transfer the fine distinction between recognizable and decidable. Turing reductions are looser and can prove undecidability in cases a single clean mapping cannot, but the very flexibility that lets them flip the answer means they do NOT respect that fine line: a Turing reduction can connect a problem to its complement, so it cannot tell recognizable from co-recognizable. Honest rule of thumb: every mapping reduction is a (very disciplined) Turing reduction, but not the reverse. When you only need 'B is undecidable', either works; when you need 'B is unrecognizable', reach for a mapping reduction.
A gallery of the condemned
With the lever in hand, the list of undecidable problems grows fast — and a guided tour of the gallery shows how far the halting problem's shadow reaches. Among Turing-machine questions, EMPTINESS (does this machine accept NO strings at all?) and EQUIVALENCE (do these two machines accept exactly the same language?) are both undecidable; each falls to a reduction from acceptance. These are not 'merely slow' problems we could solve with a faster computer — they have no correct general algorithm AT ALL, the same hard sense in which the halting problem is impossible. Be careful not to soften that: undecidable means provably no algorithm, not 'hard in practice'.
Some of the most useful undecidable problems do not mention machines at all. The star of the next two guides is the Post correspondence problem: you are given a stack of domino-like tiles, each carrying a top string and a bottom string, and you must decide whether some sequence of tiles (repeats allowed) makes the concatenated top read the same as the concatenated bottom. It sounds like an innocent word puzzle, yet the Post correspondence problem is undecidable — and because it is purely about string-matching, it becomes the perfect weapon for attacking questions about grammars. Several natural grammar problems die at its hand, most famously deciding whether two context-free grammars generate the same language, or whether a given grammar is ambiguous.
There is also a wholesale theorem that condemns properties in bulk: Rice's theorem. It says that ANY nontrivial property of the LANGUAGE a machine recognizes is undecidable — 'does this machine accept a finite language?', 'is its language empty?', 'does it recognize the primes?' all fall at once. The crucial fine print, easy to misread: Rice's theorem is about properties of the LANGUAGE (the input/output behaviour), not about syntactic properties of the code. 'Does this machine have exactly 12 states?' or 'does its description contain the letter q?' are perfectly decidable — you just inspect the text. Rice bites only when the question is about WHAT the machine computes, not HOW it is written.
The recursion theorem: a machine that knows itself
There is one last tool this rung introduces, and it feels like a magic trick until you see the gears. The recursion theorem says: any machine can be given access to its OWN description, for free. More precisely, if you can describe a computation that wants to use 'my own source code' as a value, then a real machine exists that does exactly that, with its own complete description handed to it on the tape. This sounds circular — how can a program contain its own text, which would then have to contain that text, forever? — but it is genuinely possible, and the smallest example is a quine, a program whose only job is to print its own source.
The recursion theorem wears two hats. As a PROOF TOOL it makes self-reference respectable and clean: instead of the fiddly diagonalization gymnastics, you may simply say 'let M be a machine that obtains its own description and then does the following...', and the theorem guarantees such an M exists. This streamlines the proof that the halting problem is undecidable: build a machine that asks the supposed halt-checker about ITSELF and then deliberately does the opposite — halting if predicted to loop, looping if predicted to halt — a contradiction that needs the machine to hold its own description, exactly what the theorem supplies. As a RESULT, it is a deep statement that self-reference is not paradoxical but a built-in, harmless capability of computation.
Reduction layout (the shape of every proof in this rung):
KNOWN-undecidable ----- reduces to -----> YOUR new problem
A_HP B
(halting problem) f (your target)
To prove B undecidable, BUILD this translator:
assume a decider R for B (the hypothetical magic solver)
construct decider S for A_HP:
on input <M, w>:
1. transform <M, w> into an instance x of B <- you write f
2. run R on x
3. report R's answer (possibly flipped) as the answer for A_HP
Then S decides the halting problem -- IMPOSSIBLE.
So R cannot exist, hence B is undecidable.
Arrow points FROM the known-hard problem INTO your new one.
Reverse it and the proof collapses to nothing.What to carry up the ladder
Step back and see what just changed. Before this guide, undecidability was a handful of hand-built results sitting in isolation. Now you have a manufacturing process: identify a known-impossible problem, write a translator that converts ITS questions into questions about your target, and the impossibility flows downhill into your target for free. That single act — proving undecidability by reduction — is the workhorse of the entire theory of the unsolvable, and the same shape, with 'undecidable' swapped for 'NP-hard' and 'computable function' tightened to 'polynomial-time function', will return to power the theory of intractability later in the ladder.
Carry three honest cautions with you. First, direction is sacred: reduce the KNOWN-hard problem TO your new one, never the reverse, or you prove nothing — this is the error to watch for above all. Second, undecidable means truly no algorithm, not slow or merely difficult, and Rice's theorem bites only on properties of the LANGUAGE, not on plainly-readable syntax of the code. Third, the flavours differ: mapping reductions are strict enough to transfer undecidability AND unrecognizability, while the looser Turing reduction can flip answers and so cannot tell recognizable from co-recognizable. The next guide makes the mapping reduction fully precise and watches hardness spread through it step by step.