More Undecidable Problems
Rice’s TheoremPost’s Correspondence ProblemSome Real Problems
Properties of Languages
Any set of languages is apropertyof languages.Example: The infiniteness property is the set of infinite languages.
Properties of Langauges – (2)
As always, languages must be defined by some descriptive device.The most general device we know is the TM.Thus, we shall think of a property as aproblemabout Turing machines.Let LPbe the set of binary TM codes for TM’s M such that L(M) has property P.
There are two (trivial) properties P for which LPis decidable.Thealways-false property, which contains no RE languages.Thealways-true property, which contains every RE language.Rice’s Theorem: For every other property P, LPis undecidable.
Plan for Proof of Rice’s Theorem
Lemma needed: recursive languages are closed under complementation.We need the technique known asreduction, where an algorithm converts instances of one problem to instances of another.Then, we can prove the theorem.
Closure of Recursive Languages Under Complementation
If L is a language with alphabetΣ*, then thecomplementof L isΣ* - L.Denote the complement of L by Lc.Lemma: If L is recursive, so is Lc.Proof: Let L = L(M) for a TM M.Construct M’ for Lc.M’ has one final state, the new state f.
M’ simulates M.But if M enters an accepting state, M’ halts without accepting.If M halts without accepting, M’ instead has a move taking it to state f.In state f, M’ halts.
Areductionfrom language L to language L’ is an algorithm (TM that always halts) that takes a string w and converts it to a string x, with the property that:x is in L’ if and only if w is in L.
We have regarded TM’s as acceptors of strings.But we could just as well visualize TM’s as having anoutput tape, where a string is written prior to the TM halting.Such a TM translates its input to its output.
Reductions – (2)
If we reduce L to L’, and L’ is decidable, then the algorithm for L’ + the algorithm of the reduction shows that L is also decidable.Used in the contrapositive: If we know L is not decidable, then L’ cannot be decidable.
This form of reduction is not the most general.Example: We “reduced” Ldto Lu, but in doing so we had to complement answers.More in NP-completeness discussion onKarp vs. Cook reductions.
Proofof Rice’s Theorem
We shall show that for every nontrivial property P of the RE languages, LPis undecidable.We show how to reduce Luto LP.Since we know Luis undecidable, it follows that LPis also undecidable.
Our reduction algorithm must take M and w and produce a TM M’.L(M’) has property P if and only if M accepts w.M’ has two tapes, used for:Simulates another TM MLon the input to M’.Simulates M on w.Note: neither M, ML, nor w is input to M’.
The Reduction – (2)
Assume thatdoes not have property P.If it does, consider the complement of P, which would also be decidable by the lemma.Let L be any language with property P, and let MLbe a TM that accepts L.M’ is constructed to work as follows (next slide).
Design of M’
On the second tape, write w and then simulate M on w.If M accepts w, then simulate MLon the input x to M’, which appears initially on the first tape.M’ accepts its input x if and only if MLaccepts x.
Action of M’ if M Accepts w
Simulate Mon input w
Simulate MLon input x
Acceptiff x isin ML
Design of M’ – (2)
Suppose M accepts w.Then M’ simulates MLand therefore accepts x if and only if x is in L.That is, L(M’) = L, L(M’) has property P, and M’ is in LP.
Design of M’ – (3)
Suppose M does not accept w.Then M’ never starts the simulation of ML, and never accepts its input x.Thus, L(M’) =, and L(M’) does not have property P.That is, M’ is not in LP.
Action of M’ if M Does not Accept w
Simulate Mon input w
Never accepts, sonothing else happensand x is not accepted
Design of M’ – Conclusion
Thus, the algorithm that converts M and w to M’ is a reduction of Luto LP.Thus, LPis undecidable.
Picture of the Reduction
Hypotheticalalgorithm forproperty P
Acceptiff Maccepts w
This would be an algorithmfor Lu, which doesn’t exist
Applications of Rice’s Theorem
We now have any number of undecidable questions about TM’s:Is L(M) a regular language?Is L(M) a CFL?Does L(M) include any palindromes?Is L(M) empty?Does L(M) contain more than 1000 strings?Etc., etc.