Many-one reduction
A total computable transformation that preserves yes/no membership as displayed. A solver for B would then solve A after transforming the input.
Find a concept
REFERENCE SHEET
Reductions & undecidability
Transfer impossibility by showing how a hypothetical solver would solve a known impossible problem.
Before this Turing machines, deciders & recognizers
A ≤ₘ B: ∃ total computable f, x∈A ⇔ f(x)∈B
Definitions
Halting problem
HALT={⟨M,w⟩: machine M halts on input w}. It asks about halting, not specifically acceptance.
Semantic property
A property of the language recognized by a machine rather than of the syntax or particular implementation of its description.
Key theorems
Undecidability of HALT
No Turing-machine decider correctly answers halting for every machine–input pair. Diagonalization constructs a program that contradicts a purported universal halting decider.
Reduction transfer
If A≤ₘB and B is decidable, A is decidable. Equivalently, if A is undecidable, such a reduction proves B undecidable.
Rice theorem
Every nontrivial property of Turing-recognizable languages has an undecidable machine-description index set. Nontrivial means it holds for some recognizable language and fails for another.
Notable applications
Program analysis
Universal, always-terminating, exact semantic analysis is impossible for many properties of unrestricted programs.
Tool design
Use restricted languages, bounded exploration, or conservative approximations when exact general analysis cannot terminate on every input.
Work it out
Try before revealing01 / Construct a reduction
Reduce HALT to the problem “does machine N accept at least one string?”
Hint
Make N ignore its own input and simulate the given instance.
Solution
From ⟨M,w⟩, construct N that on any input simulates M(w), then accepts if that simulation halts. If M halts, N accepts every string; otherwise it accepts none. This computable construction proves the target undecidable.
02 / Apply or reject
Does Rice apply to “the recognized language is empty”? To “the description has at most ten states”?
Hint
Ask whether the property depends only on the language.
Solution
Emptiness is a nontrivial semantic language property, so Rice applies. State count is syntactic and not invariant under replacing a machine by an equivalent one; Rice does not apply. State count is decidable by inspecting the finite description.
Connect the ideas
Go deeper
Further reading and full-length treatments: