Suppose you have proved, once and with great effort, that one problem is impossible to solve. Do you have to start from scratch for the next problem? No. If you can show that a solution to the new problem would give you a solution to the old, impossible one, then the new problem must be impossible too. This idea is called a reduction, and it is how almost every undecidability result after the halting problem is proved.
In Halting Problem & Undecidability we proved by diagonalization that ATM and HALTTM are undecidable. In this chapter we use them as the "known hard" problems and reduce them to many others: halting on a blank tape, emptiness, regularity and equivalence of TMs. Then we prove Rice's theorem, which handles a whole family of such questions in one stroke.
A problem A reduces to a problem B if any method for solving B can be turned into a method for solving A. If A reduces to B and A is undecidable, then B is undecidable.
The Idea of a Reduction
An everyday example: finding your way in a new city reduces to having a map. If you have a map, you can find your way. Notice the direction: the reduction shows that the second thing (the map) is at least as powerful as the first.
In computability we use reductions in the "negative" direction:
A reduces to B ("B is at least as hard as A")
If B is decidable ==> A is decidable
If A is undecidable ==> B is undecidable (contrapositive, the useful one)So to prove a new problem B undecidable, we pick a problem A already known to be undecidable (usually ATM or HALTTM) and show A reduces to B. The single most common exam mistake is doing it the other way round. Reducing B to A ("B can be solved using A") tells us nothing about B, because A is unsolvable anyway.
Rule of thumb: to show B is hard, reduce a known hard problem TO B. Arrows point from the known problem to the new one.
Mapping Reductions
The cleanest kind of reduction transforms each instance of A into an instance of B with the same answer.
A language A is mapping-reducible (many-one reducible) to B, written A ≤m B, if there is a computable function f : Σ* → Σ* such that for every string w, w ∈ A if and only if f(w) ∈ B. The function f is called the reduction.
"Computable" means some TM computes f(w) from w and always halts. Note that f does not solve anything: it only rewrites the question. The "if and only if" is essential: yes-instances must map to yes-instances and no-instances to no-instances.
f
A ----------> B
yes ------> yes
no ------> no (f must be computable and always halt)What a mapping reduction gives you
If A ≤m B and … | then … | Reason |
|---|---|---|
B is decidable (recursive) | A is decidable | On w, compute f(w) and run B's decider. |
B is RE | A is RE | On w, compute f(w) and run B's recogniser. |
A is undecidable | B is undecidable | Contrapositive of row 1. |
A is not RE | B is not RE | Contrapositive of row 2. |
Two more useful facts:
A ≤m B if and only if Ā ≤m B̄ (the same f works for the complements, because of the "if and only if").
≤m is transitive: if A ≤m B and B ≤m C then A ≤m C (compose the functions).
Things that do not follow: from A ≤m B, "A decidable" says nothing about B, and "B undecidable" says nothing about A.
Turing reductions (briefly)
A more general notion is the Turing reduction A ≤T B: A can be decided by a TM that may ask an imaginary "oracle" for B any number of questions. Our argument "a HALT decider gives an ATM decider" in the previous chapter was of this kind. Turing reductions preserve decidability but not RE-ness: for example the complement of ATM is Turing-reducible to ATM (ask the oracle, flip the answer), yet ATM is RE and its complement is not. For proving non-RE results we therefore use mapping reductions.
The Standard Trick: Build a Machine That Ignores Its Input
Most reductions from ATM follow one pattern. Given ⟨M, w⟩, the reduction writes down the description of a new machine M′ that has M and w hard-wired into it. f does not run M; it just builds M′ as text, which is always possible and always finishes. M′ is designed so that its behaviour (or its language) depends on whether M accepts w.
The most used gadget is:
M_w, on any input x:
1. Ignore x.
2. Run M on w.
3. If M accepts w, ACCEPT.
L(M_w) = Σ* if M accepts w
L(M_w) = ∅ if M does not accept w (M rejects or loops)So a question about L(Mw) secretly asks "does M accept w?". Let us use this.
Worked Reductions
1. HALTTM is undecidable (ATM ≤m HALTTM)
Given ⟨M, w⟩, build M′: "on input x, run M on x; if M accepts, accept; if M rejects, go into an infinite loop". Output f(⟨M, w⟩) = ⟨M′, w⟩.
M on w | M′ on w | ⟨M, w⟩ ∈ ATM? | ⟨M′, w⟩ ∈ HALTTM? |
|---|---|---|---|
accepts | accepts (halts) | yes | yes |
rejects | loops | no | no |
loops | loops | no | no |
The answers match in every case, so ATM ≤m HALTTM and HALTTM is undecidable. (Turning "reject" into "loop" is the whole trick.)
2. The blank-tape halting problem is undecidable
HALTε = { ⟨M⟩ : M halts when started on a blank tape }. Reduce HALTTM to it: given ⟨M, w⟩, build Mw: "erase the tape, write w, move back to the start, then behave like M". Mw halts on the blank tape exactly when M halts on w. So HALTTM ≤m HALTε, and HALTε is undecidable. Knowing the input in advance does not help.
3. Emptiness ETM is undecidable, and not even RE
ETM = { ⟨M⟩ : L(M) = ∅ }. Use the gadget Mw: f(⟨M, w⟩) = ⟨Mw⟩. Then
M accepts w <=> L(M_w) = Σ* <=> L(M_w) ≠ ∅
M doesn't accept <=> L(M_w) = ∅ <=> <M_w> ∈ E_TMSo f maps the complement of ATM to ETM: ĀTM ≤m ETM. Since ĀTM is not RE, ETM is not RE (and hence undecidable). Equivalently ATM ≤m NETM, where NETM = { ⟨M⟩ : L(M) ≠ ∅ }.
NETM itself is RE: a recogniser can run M on all strings in parallel, using dovetailing (in round k, run k steps of M on each of the first k strings) and accept as soon as any run accepts. So NETM is RE but not recursive, and ETM is not RE.
4. REGULARTM is undecidable
REGULARTM = { ⟨M⟩ : L(M) is a regular language }. Here the "ignore input" gadget is not enough (∅ and Σ* are both regular), so we mix in a non-regular language. Given ⟨M, w⟩, build:
R, on input x:
1. If x has the form 0^n 1^n, ACCEPT.
2. Otherwise run M on w; if M accepts w, ACCEPT.
M accepts w => L(R) = Σ* (regular)
M doesn't accept => L(R) = { 0^n 1^n } (not regular)So ⟨M, w⟩ ∈ ATM ⟺ ⟨R⟩ ∈ REGULARTM, and REGULARTM is undecidable. Replacing "regular" by "context-free" (use { 0n1n2n } as the default language) shows that "is L(M) context-free?" is undecidable too.
5. Equivalence EQTM is undecidable
EQTM = { ⟨M1, M2⟩ : L(M1) = L(M2) }. If we could test equivalence we could test emptiness: fix a machine M∅ that rejects everything and map ⟨M⟩ to ⟨M, M∅⟩. Then L(M) = ∅ ⟺ L(M) = L(M∅). So ETM ≤m EQTM, and since ETM is not RE, EQTM is not RE. (Its complement is not RE either, so EQTM is in neither class.)
Rice's Theorem
Look back at ETM, REGULARTM and EQTM. Every proof used the same idea, and every question was about what language the machine accepts, not about how the machine is built. Rice's theorem (H. G. Rice, 1953) says that all such questions are undecidable, except the trivial ones.
Properties of languages
A property P of RE languages is simply a set of RE languages (the ones that "have" the property). The corresponding problem is LP = { ⟨M⟩ : L(M) ∈ P }. P is trivial if it holds for all RE languages or for none; otherwise it is non-trivial.
Such a property is semantic: if L(M1) = L(M2), then ⟨M1⟩ and ⟨M2⟩ are either both in LP or both out. Examples: "L(M) is empty", "L(M) contains the string 01", "L(M) is finite", "L(M) is regular".
Rice's Theorem. Every non-trivial property of the recursively enumerable languages is undecidable. That is, if P is non-trivial, then LP = { ⟨M⟩ : L(M) ∈ P } is not recursive.
Proof
Let P be non-trivial.
Assume ∅ ∉ P. (If ∅ ∈ P, work with the complementary property P̄, which is also non-trivial and does not contain ∅. If LP̄ is undecidable then so is LP, since recursive languages are closed under complement; LP̄ is exactly the set of TM codes not in LP.)
Because P is non-trivial, some RE language is in P. Fix a TM T with L(T) ∈ P.
Reduce ATM to LP. Given ⟨M, w⟩, build:
M', on input x:
1. Run M on w. If M rejects or loops, so does M' (never accepts).
2. If M accepted w, run T on x and ACCEPT if T accepts.
M accepts w => L(M') = L(T) which IS in P
M doesn't accept => L(M') = ∅ which is NOT in PStep 4. So ⟨M, w⟩ ∈ ATM ⟺ ⟨M′⟩ ∈ LP. Building ⟨M′⟩ from ⟨M, w⟩ is a simple computable transformation. Hence ATM ≤m LP, and LP is undecidable. ∎
How to apply Rice's theorem (checklist)
Is the question only about L(M)? (Would two machines with the same language always get the same answer?) If it mentions states, steps, head moves or the tape, Rice does not apply.
Is it non-trivial? Find one TM whose language has the property and one whose language does not.
If both are yes, the problem is undecidable.
Solved examples
Problem: given a TM M, … | About L(M) only? | Non-trivial? | Verdict |
|---|---|---|---|
is L(M) = ∅? | Yes | Yes (∅ has it, Σ* doesn't) | Undecidable (Rice) |
is L(M) finite? | Yes | Yes ({a} vs Σ*) | Undecidable (Rice) |
is L(M) regular? context-free? recursive? | Yes | Yes | Undecidable (Rice) |
does L(M) contain the string 0110? | Yes | Yes | Undecidable (Rice) |
is L(M) = Σ*? does L(M) have exactly 5 strings? | Yes | Yes | Undecidable (Rice) |
is L(M) recursively enumerable? | Yes | No: every L(M) is RE | Decidable (always "yes") |
does M have at most 10 states? | No (about the machine) | - | Decidable: read ⟨M⟩ and count |
does M take more than 100 steps on some input? | No | - | Decidable: in its first 101 steps M can look at only the first 101 tape cells, so it is enough to run M for 101 steps on every input of length ≤ 101 (finitely many) |
does M halt on input w? | No (halting is not a language property) | - | Undecidable, but by the halting problem, not by Rice |
does M halt on every input (is M a decider)? | No (two machines with the same language can differ) | - | Undecidable, by reduction (it is neither RE nor co-RE) |
Notice the last two rows: Rice's theorem gives undecidability only for semantic, non-trivial properties. When it does not apply, the problem may be decidable (rows 6-8) or undecidable for other reasons (rows 9-10).
Rice for RE: when is LP not even RE?
A stronger result (the Rice–Shapiro theorem) describes which properties are RE. One easy consequence is enough for exams:
If there are RE languages L1 ⊆ L2 with L1 ∈ P but L2 ∉ P, then LP is not RE.
Intuition: a recogniser only ever sees finitely many accepted strings before it answers, so it cannot "un-accept" when the language grows. Examples:
L(M) = ∅: ∅ ∈ P but Σ* ⊇ ∅ is not, so ETM is not RE (matching worked reduction 3).
L(M) is finite: {a} ∈ P but Σ* ∉ P, so not RE.
L(M) ≠ ∅ and L(M) contains 0110 are "upward closed" and in fact RE (search for an accepted string by dovetailing), though undecidable.
Decidability of Standard Problems: The Big Table
Combining this chapter with the earlier decision-property chapters, and with results from Post Correspondence Problem (next chapter), gives the table GATE questions are built from. D = decidable, U = undecidable.
Problem | Regular | DCFL | CFL | CSL | Recursive | RE |
|---|---|---|---|---|---|---|
Membership (w ∈ L?) | D | D | D | D | D | U |
Emptiness (L = ∅?) | D | D | D | U | U | U |
Finiteness | D | D | D | U | U | U |
Universality (L = Σ*?) | D | D | U | U | U | U |
Equivalence (L1 = L2?) | D | D | U | U | U | U |
Containment (L1 ⊆ L2?) | D | U | U | U | U | U |
Is L1 ∩ L2 = ∅? | D | U | U | U | U | U |
Is L regular? | D (trivially yes) | D | U | U | U | U |
Notes on the less obvious entries:
The languages are given by their machines or grammars (DFA, DPDA, CFG, LBA, decider, TM).
DCFL equivalence was a long-open problem, shown decidable by Géraud Sénizergues (1997). DCFL universality is easy because DCFLs are closed under complement.
For CFLs, universality, equivalence, containment, intersection-emptiness and regularity are undecidable; several of these are proved from PCP in the next chapter. Ambiguity of a CFG is also undecidable.
For an RE language, membership is undecidable but semi-decidable (the TM accepts exactly the members).
Common Mistakes
Reducing in the wrong direction. To show B undecidable, reduce ATM (known) to B, i.e. ATM ≤m B. Showing B ≤m ATM only proves B is RE.
Letting the reduction run M. f must always halt, so it may only build a machine description containing M and w. Running M happens later, inside M′, and that is allowed to loop.
Forgetting the "only if" direction. Checking that yes-instances map to yes-instances is half a proof; no-instances must map to no-instances.
Applying Rice to properties of the machine. "M has 7 states", "M ever writes symbol X", "M runs more than 50 steps on input 0" are about the machine or its running time, not about L(M). Rice says nothing; many of these are decidable.
Forgetting non-triviality. "L(M) is RE" is trivial (true for every TM), hence decidable.
Thinking Rice applies to DFAs or CFGs. Rice's theorem is about TMs (RE languages). For DFAs, emptiness, finiteness and equivalence are all decidable.
Concluding "decidable" from A ≤m B and A decidable. Reductions transfer decidability from B down to A, never upwards.
GATE and Interview Questions
Q1. A ≤m B. Which of these must be true? (a) If A is RE then B is RE. (b) If B is RE then A is RE. (c) If A is recursive then B is recursive. (d) If B is not RE then A is not RE.
Only (b). Reductions transfer "easiness" from B to A, and "hardness" from A to B. (a) and (c) go the wrong way; (d) is the contrapositive of the wrong-way statement. The correct hardness statement is "if A is not RE then B is not RE".
Q2. Which of the following are undecidable? (i) Given a TM M, is L(M) finite? (ii) Given a TM M, does M have an even number of states? (iii) Given a TM M, is L(M) = {ε}? (iv) Given a DFA D, is L(D) finite?
(i) and (iii), by Rice's theorem (both are non-trivial properties of L(M)). (ii) is about the machine's description, decidable by counting. (iv) is decidable for DFAs: L(D) is infinite iff there is a cycle on some path from the start state to a final state.
Q3. Prove that "does M accept the string ε?" is undecidable without using Rice's theorem.
Reduce ATM: from ⟨M, w⟩ build Mw, which ignores its input, runs M on w and accepts if M accepts. Mw accepts ε ⟺ M accepts w. The construction is computable, so ATM ≤m { ⟨M⟩ : ε ∈ L(M) }.
Q4. Is ETM = { ⟨M⟩ : L(M) = ∅ } RE? Is its complement RE?
ETM is not RE; its complement NETM is RE (dovetail M over all strings and accept when some run accepts). The reduction ĀTM ≤m ETM shows ETM is not RE.
Q5. Why can't Rice's theorem be used to prove the halting problem undecidable?
"M halts on w" is not a property of the language L(M): two machines can accept the same strings while one rejects w and the other loops on w. Rice only covers properties that depend on L(M) alone.
Q6. Which problems about CFGs are decidable: emptiness, finiteness, membership, equivalence, ambiguity?
Emptiness, finiteness and membership are decidable (useful-symbol test, cycle test on a reduced grammar, CYK). Equivalence and ambiguity are undecidable.
Q7. Interview: why do static analysers give false positives?
By Rice's theorem every non-trivial question about a program's input/output behaviour is undecidable. A tool that always terminates must therefore approximate: if it is designed never to miss a real bug (sound), it must sometimes warn about correct code.
Summary
A mapping reduction A ≤m B is a computable f with w ∈ A ⟺ f(w) ∈ B.
If A ≤m B: B decidable ⟹ A decidable; B RE ⟹ A RE; A undecidable ⟹ B undecidable; A not RE ⟹ B not RE.
To prove B undecidable, reduce a known undecidable problem (ATM, HALTTM) to B.
Key gadget: Mw ignores its input and runs M on w, so L(Mw) is Σ* or ∅.
Using it: HALTTM, blank-tape halting, ETM (not RE), REGULARTM and EQTM (neither RE nor co-RE) are undecidable.
Rice's theorem: every non-trivial property of the language L(M) of a TM is undecidable. It does not apply to properties of the machine itself or to trivial properties.
If a property holds for some L1 but fails for a superset L2, the problem is not even RE.
Reductions carry hardness forward: show that solving the new problem would solve an old impossible one. Rice's theorem does this once for every question about what a program accepts.