Publish on 03rd November 2019
Category: Birds
0

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

CS154 slides - ics.uci.edu