1
More Undecidable Problems
Rice’s TheoremPost’s Correspondence ProblemSome Real Problems
2
Properties of Languages
Any set of languages is apropertyof languages.Example: The infiniteness property is the set of infinite languages.
3
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.
4
Trivial Properties
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.
5
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.
6
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.
7
Proof– Concluded
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.
8
Reductions
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.
9
TM’s asTransducers
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.
10
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.
11
Reductions –Aside
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.
12
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.
13
The Reduction
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’.
14
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).
15
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.
16
Action of M’ if M Accepts w
Simulate Mon input w
x
Simulate MLon input x
On accept
Acceptiff x isin ML
17
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.
18
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.
19
Action of M’ if M Does not Accept w
Simulate Mon input w
x
Never accepts, sonothing else happensand x is not accepted
20
Design of M’ – Conclusion
Thus, the algorithm that converts M and w to M’ is a reduction of Luto LP.Thus, LPis undecidable.
21
Picture of the Reduction
A realreductionalgorithm
M, w
Hypotheticalalgorithm forproperty P
M’
Acceptiff Maccepts w
Otherwisehalt withoutaccepting
This would be an algorithmfor Lu, which doesn’t exist
22
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.
0
Embed
Upload