Reducibility & Advanced Undecidability

proving undecidability by reduction

Once you have a single problem proved impossible from scratch, you rarely have to do that hard work again. Undecidability spreads by contagion. The technique is to argue: if I could solve this new problem, then I could solve the halting problem, which is impossible, so this new problem must be impossible too. It is proof by 'if you could, then so could I, but I cannot, so neither can you'. The known impossibility is the seed; reduction is the wind that carries it everywhere.

The recipe has a fixed shape. To prove a new problem B is undecidable: (1) pick a problem A that is already known undecidable, classically the acceptance problem A_TM or the halting problem; (2) assume for contradiction that B has a decider, a machine that always halts with the correct yes or no; (3) using that hypothetical B-decider as a subroutine, build a decider for A; (4) but A has no decider, contradiction, so B has no decider either. Steps (2) and (3) together are exactly the reduction A <= B, often realized as a mapping reduction: a computable function turning each A-instance into a B-instance with yes preserved as yes. The whole argument is a proof by contradiction wrapped around a reduction.

Getting the direction right is everything: you reduce the known-hard A to your new B, never the reverse (see the direction of a reduction). Done correctly, this single template indicts a whole gallery of problems: emptiness, equivalence, regularity, and totality for Turing machines, and through the Post correspondence problem, a slew of grammar problems. There is also a slicker alternative route using the recursion theorem, which builds a self-referential machine directly and sidesteps the explicit reduction, but the reduction template is the one you reach for most.

Prove HALT (does M halt on w?) is undecidable assuming A_TM is. Suppose H decides HALT. Build a decider for A_TM: given (M, w), first ask H whether M halts on w; if H says no, reject; if H says yes, simulate M on w to completion and accept iff M accepts. This always halts and decides A_TM, contradicting its undecidability. So HALT is undecidable.

Assume a decider for the new problem, use it to decide a known-undecidable one, reach a contradiction.

The contradiction comes from the KNOWN-undecidable problem, so you must reduce that known problem to your new one (A <= B), not the reverse. Reverse it and the proof is empty.

Also called
reduction proof of undecidabilityspreading undecidability傳播不可判定性