Undecidability, mapping reductions and Rice’s theorem
Goals and conventions
Prove undecidability by contradiction and use reductions in the correct direction. Machines have effective finite encodings; malformed encodings are rejected in the decision problems discussed here. A_TM asks whether M accepts w; HALT_TM asks whether M eventually halts on w, either accepting or rejecting. Acceptance and halting are different events. “Undecidable” means no algorithm correctly halts with a yes/no answer on every instance; it does not mean every instance is impossible to settle.
1. Diagonal proof for acceptance
Suppose a decider H for A_TM exists. Construct a machine D which on a valid machine encoding ⟨M⟩ runs H on ⟨M,⟨M⟩⟩. If H says yes, D rejects; if H says no, D accepts. On an invalid encoding D immediately rejects. D halts on every input because H does. Now run D on its own encoding. If H predicts D accepts ⟨D⟩, D rejects; if H predicts it does not accept, D accepts. Both possibilities contradict H's correctness. Therefore A_TM is undecidable. Self-input is legitimate because machine descriptions are finite strings that machines can receive as input.
A_TM is nevertheless recognizable by universal simulation. Its complement is not recognizable: otherwise the two-recognizer theorem would make A_TM decidable. This separates undecidability from nonrecognizability.
2. Mapping reductions and direction
A≤m B means there is a total computable function f such that for every x, x∈A iff f(x)∈B. To solve A using a hypothetical B decider, compute f(x), then ask the B decider. Consequently, if A is undecidable and A≤m B, then B is undecidable. Reducing B to known-hard A does not prove B hard; easy problems can reduce to hard ones.
The function must halt for every x, and it must preserve both yes and no cases. It normally outputs a machine description rather than running the encoded machine to completion. If B is recognizable and A≤m B, A is recognizable by computing f and invoking B's recognizer. Taking the contrapositive can prove nonrecognizability, not just undecidability.
3. Worked reduction from acceptance to halting
Given ⟨M,w⟩, construct N that ignores its own input and simulates M on w. If M accepts, N halts accepting. If M rejects, N deliberately enters an infinite loop; if M loops, N keeps simulating forever. Output ⟨N,ε⟩. Writing this finite program description is a terminating transformation; the reducer itself does not wait for M to accept.
M accepts w iff N halts on ε. Thus A_TM≤m HALT_TM, and HALT_TM is undecidable. For a malformed source encoding output a fixed machine/input pair that never halts, preserving the no case. A tempting construction “N simply simulates M” fails for this reduction because M might reject w and halt: that is a no-instance of acceptance but a yes-instance of halting.
4. Language properties and Rice’s theorem
Rice’s theorem: every nontrivial semantic property of the language recognized by a TM is undecidable. Semantic means machines recognizing the same language agree on the property; nontrivial means some recognizable language has it and another recognizable language does not. Examples include whether L(M) is empty, finite, regular, or contains a fixed word. Rice does not directly apply to syntactic properties such as “the description has five states,” or operational properties such as “M halts on every input,” because those are not determined solely by L(M). A problem outside Rice's hypotheses can still be undecidable by another argument.
Worked nonemptiness reduction: given ⟨M,w⟩, build N that on input x simulates M(w), accepting x if that simulation accepts and never accepting otherwise. If M accepts w, L(N)=Σ*; otherwise L(N)=∅. For a malformed source encoding, output a fixed reject-all machine, so every invalid source maps to a no-instance of NONEMPTY_TM. This makes the transformation total on all strings and proves A_TM≤m NONEMPTY_TM. NONEMPTY_TM is recognizable by dovetailing M on all input strings and accepting when any simulation accepts. EMPTY_TM is undecidable and not recognizable: if both it and its recognizable complement were recognizable, emptiness would be decidable. These are complements relative to valid machine encodings; malformed encodings can be handled separately by a terminating syntax check without changing the results.
5. Choosing the right proof tool
For DFA membership, emptiness and equivalence, finite graph algorithms terminate. For CFG membership and emptiness, finite grammar algorithms terminate; general equivalence and ambiguity are undecidable. For arbitrary TM descriptions, language semantics trigger stronger impossibility results. Always identify both the representation and the question. The language ∅ is decidable, while the set of TM descriptions whose recognized language equals ∅ is undecidable: these are two different languages at different encoding levels.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. To prove B undecidable using known-undecidable A, which direction is useful?
A. B≤m A only B. A≤m B C. Neither direction can help D. Equality of alphabet sizes alone
Answer: B
A: This does not transfer hardness to B.
B: A B-decider would then yield an impossible A-decider.
C: Mapping reductions are a standard tool here.
D: Alphabet size does not establish computational hardness.
P02. A mapping reduction function must be:
A. Allowed to loop on no-instances B. Total computable and yes/no preserving C. An oracle for the source language D. Injective in every reduction
Answer: B
A: It must produce an output for every input.
B: These are the defining requirements.
C: The transformation must itself be computable.
D: Injectivity is not required.
P03. In the A_TM to HALT_TM reduction, if M rejects w, N must:
A. Halt rejecting B. Halt accepting C. Loop forever D. Return M’s reject result immediately
Answer: C
A: That would incorrectly create a halting yes-instance.
B: That also creates a halting yes-instance.
C: A source no-instance must map to nonhalting.
D: Returning is halting and breaks the reduction.
P04. Which is a nontrivial semantic language property covered by Rice?
A. The encoding has an even length B. The machine has exactly five states C. L(M) is finite D. The machine executes exactly seven steps on ε
Answer: C
A: Encoding length is syntactic.
B: State count is syntactic.
C: Finiteness depends only on the recognized language and is nontrivial.
D: Step counts are operational, not determined by L(M).
P05. Why is complement(A_TM) not recognizable?
A. A_TM is not recognizable B. Both recognizers would give an A_TM decider C. All complements are unrecognizable D. Its strings are infinite
Answer: B
A: A_TM is recognizable by simulation.
B: Dovetailing would contradict A_TM undecidability.
C: Complements of decidable languages are decidable.
D: Machine/input encodings are finite strings.
P06. Which comparison is correct?
A. ∅ is undecidable because EMPTY_TM is B. ∅ is decidable but EMPTY_TM is undecidable C. Both questions are identical D. EMPTY_TM asks whether the input string is empty
Answer: B
A: A decider can reject every input for ∅.
B: One concerns words in ∅; the other concerns machine descriptions.
C: They operate at different encoding levels.
D: It asks whether the encoded machine accepts no strings.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Theory of Computation syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in