• No results found

Rice’s Theorem

N/A
N/A
Protected

Academic year: 2022

Share "Rice’s Theorem"

Copied!
28
0
0

Loading.... (view fulltext now)

Full text

(1)

CS310 : Automata Theory 2019

Lecture 31: Rice’s theorem and other undecidable problems

Instructor: S. Akshay

IITB, India

(2)

Recap

Turing machines and computability

1. Definition of Turing machines: high level and low-level descriptions 2. Variants of Turing machines

3. Decidable and Turing recognizable languages 4. Church-Turing Hypothesis

5. Undecidability and a proof technique by diagonalization

I A universal TM langLATM ={hM,wi |M is a TM andM acceptsw} 6. Reductions: a powerful way to show undecidability.

7. Rice’s theorem

(3)

Rice’s Theorem

Let P be a non-trivial property of r.e. languages. Then LP ={hMi |L(M)∈P} is undecidable.

For the following, is Rice’s theorem applicable?

1. {hMi |M runs for 5 steps on word 010}. 2. {hMi |M has at most 25 states.}.

3. {hMi |L(M) is recognized by a TM with at least 25 states.}. 4. {hMi |L(M) is recognized by a TM with at most 25 states and tape

alphabet at most 10.}. 5. {hMi |L(M) is infinite.}.

6. {hMi |M with alphabet{0,1,t}ever prints three consecutive 10s on the tape}.

I For No answers, language can still be decidable or undecidable. I If Rice’s theorem does not apply, fall back on reductions!

(4)

Rice’s Theorem

Let P be a non-trivial property of r.e. languages. Then LP ={hMi |L(M)∈P} is undecidable.

For the following, is Rice’s theorem applicable?

1. {hMi |M runs for 5 steps on word 010}. No. Property of TMs.

2. {hMi |M has at most 25 states.}. No. Property of TMs.

3. {hMi |L(M) is recognized by a TM with at least 25 states.}. No. Trivial property.

4. {hMi |L(M) is recognized by a TM with at most 25 states and tape alphabet at most 10.}. Yes.

5. {hMi |L(M) is infinite.}. Yes.

6. {hMi |M with alphabet {0,1,t} ever prints three consecutive 10s on the tape}. No. Property of TMs, but undecidable!

I For No answers, language can still be decidable or undecidable. I If Rice’s theorem does not apply, fall back on reductions!

(5)

Rice’s Theorem

Let P be a non-trivial property of r.e. languages. Then LP ={hMi |L(M)∈P} is undecidable.

For the following, is Rice’s theorem applicable?

1. {hMi |M runs for 5 steps on word 010}. No. Property of TMs.

2. {hMi |M has at most 25 states.}. No. Property of TMs.

3. {hMi |L(M) is recognized by a TM with at least 25 states.}. No. Trivial property.

4. {hMi |L(M) is recognized by a TM with at most 25 states and tape alphabet at most 10.}. Yes.

5. {hMi |L(M) is infinite.}. Yes.

6. {hMi |M with alphabet {0,1,t} ever prints three consecutive 10s on the

(6)

Proof idea

Rice’s Theorem

Let P be a non-trivial property of r.e. languages. Then LP ={hMi |L(M)∈P}is undecidable.

I Let P be a non-trivial property of r.e, such that∅ 6∈P.

I Since P is non-trivial, ∃L,ML with property P.

I IfP is decidable, there exists an algoMP for decidingP I We combine ML and MP to get algo for ATM.

I ForhM,wii/p, designhM0i, s.t L(M0)P iffM accw. I M0 is the foll:

1. ignore i/px , simulateM onw. if reject, then rejectsx. 2. if acc, then simulateMLonx, acc iffMLaccx.

I ThusM0 either acc orLdepending on ifM accw. I Thus hM0i ∈ LP iff L(M0)∈P iff L(M0) =Liff M acc w. I This gives an algo forATM so contradiction!

(7)

Proof idea

Rice’s Theorem

Let P be a non-trivial property of r.e. languages. Then LP ={hMi |L(M)∈P}is undecidable.

I Let P be a non-trivial property of r.e, such that∅ 6∈P. I Since P is non-trivial, ∃L,ML with property P.

I IfP is decidable, there exists an algoMP for decidingP I We combine ML and MP to get algo for ATM.

I ForhM,wii/p, designhM0i, s.t L(M0)P iffM accw. I M0 is the foll:

1. ignore i/px , simulateM onw. if reject, then rejectsx. 2. if acc, then simulateMLonx, acc iffMLaccx.

I ThusM0 either acc orLdepending on ifM accw. I Thus hM0i ∈ LP iff L(M0)∈P iff L(M0) =Liff M acc w. I This gives an algo forATM so contradiction!

(8)

Proof idea

Rice’s Theorem

Let P be a non-trivial property of r.e. languages. Then LP ={hMi |L(M)∈P}is undecidable.

I Let P be a non-trivial property of r.e, such that∅ 6∈P. I Since P is non-trivial, ∃L,ML with property P.

I IfP is decidable, there exists an algo MP for decidingP

I We combine ML and MP to get algo for ATM.

I ForhM,wii/p, designhM0i, s.t L(M0)P iffM accw. I M0 is the foll:

1. ignore i/px , simulateM onw. if reject, then rejectsx. 2. if acc, then simulateMLonx, acc iffMLaccx.

I ThusM0 either acc orLdepending on ifM accw. I Thus hM0i ∈ LP iff L(M0)∈P iff L(M0) =Liff M acc w. I This gives an algo forATM so contradiction!

(9)

Proof idea

Rice’s Theorem

Let P be a non-trivial property of r.e. languages. Then LP ={hMi |L(M)∈P}is undecidable.

I Let P be a non-trivial property of r.e, such that∅ 6∈P. I Since P is non-trivial, ∃L,ML with property P.

I IfP is decidable, there exists an algo MP for decidingP I We combine ML and MP to get algo for ATM.

I ForhM,wii/p, designhM0i, s.t L(M0)P iffM accw. I M0 is the foll:

1. ignore i/px , simulateM onw. if reject, then rejectsx. 2. if acc, then simulateMLonx, acc iffMLaccx.

I ThusM0 either acc orLdepending on ifM accw. I Thus hM0i ∈ LP iff L(M0)∈P iff L(M0) =Liff M acc w. I This gives an algo forATM so contradiction!

(10)

Proof idea

Rice’s Theorem

Let P be a non-trivial property of r.e. languages. Then LP ={hMi |L(M)∈P}is undecidable.

I Let P be a non-trivial property of r.e, such that∅ 6∈P. I Since P is non-trivial, ∃L,ML with property P.

I IfP is decidable, there exists an algo MP for decidingP I We combine ML and MP to get algo for ATM.

I ForhM,wii/p, designhM0i, s.t L(M0)P iffM accw.

I M0 is the foll:

1. ignore i/px , simulateM onw. if reject, then rejectsx. 2. if acc, then simulateMLonx, acc iffMLaccx.

I ThusM0 either acc orLdepending on ifM accw. I Thus hM0i ∈ LP iff L(M0)∈P iff L(M0) =Liff M acc w. I This gives an algo forATM so contradiction!

(11)

Proof idea

Rice’s Theorem

Let P be a non-trivial property of r.e. languages. Then LP ={hMi |L(M)∈P}is undecidable.

I Let P be a non-trivial property of r.e, such that∅ 6∈P. I Since P is non-trivial, ∃L,ML with property P.

I IfP is decidable, there exists an algo MP for decidingP I We combine ML and MP to get algo for ATM.

I ForhM,wii/p, designhM0i, s.t L(M0)P iffM accw. I M0 is the foll:

1. ignore i/px , simulateM onw. if reject, then rejectsx.

2. if acc, then simulateMLonx, acc iffMLaccx.

I ThusM0 either acc orLdepending on ifM accw. I Thus hM0i ∈ LP iff L(M0)∈P iff L(M0) =Liff M acc w. I This gives an algo forATM so contradiction!

(12)

Proof idea

Rice’s Theorem

Let P be a non-trivial property of r.e. languages. Then LP ={hMi |L(M)∈P}is undecidable.

I Let P be a non-trivial property of r.e, such that∅ 6∈P. I Since P is non-trivial, ∃L,ML with property P.

I IfP is decidable, there exists an algo MP for decidingP I We combine ML and MP to get algo for ATM.

I ForhM,wii/p, designhM0i, s.t L(M0)P iffM accw. I M0 is the foll:

1. ignore i/px , simulateM onw. if reject, then rejectsx.

2. if acc, then simulateMLonx, acc iffMLaccx.

I ThusM0 either acc orLdepending on ifM accw.

I Thus hM0i ∈ LP iff L(M0)∈P iff L(M0) =Liff M acc w. I This gives an algo forATM so contradiction!

(13)

Proof idea

Rice’s Theorem

Let P be a non-trivial property of r.e. languages. Then LP ={hMi |L(M)∈P}is undecidable.

I Let P be a non-trivial property of r.e, such that∅ 6∈P. I Since P is non-trivial, ∃L,ML with property P.

I IfP is decidable, there exists an algo MP for decidingP I We combine ML and MP to get algo for ATM.

I ForhM,wii/p, designhM0i, s.t L(M0)P iffM accw. I M0 is the foll:

1. ignore i/px , simulateM onw. if reject, then rejectsx.

2. if acc, then simulateMLonx, acc iffMLaccx.

I ThusM0 either acc orLdepending on ifM accw.

(14)

Proof idea

I But what ifP has∅ in it!?

I Take P. I Now ∅ 6∈P.

I Apply proof to get undecidability of LP. I Conclude undecidability of LP.

(15)

Proof idea

I But what ifP has∅ in it!?

I Take P. I Now ∅ 6∈P.

I Apply proof to get undecidability of LP. I Conclude undecidability of LP.

(16)

Proof idea

I But what ifP has∅ in it!?

I Take P. I Now ∅ 6∈P.

I Apply proof to get undecidability of LP. I Conclude undecidability of LP.

(17)

More “useful” undecidability?

Are only problems about Turing machines undecidable?

(18)

More “useful” undecidability?

Are only problems about Turing machines undecidable?

I Computers, C-programs, counter machines

(19)

More “useful” undecidability?

Are only problems about Turing machines undecidable?

I Computers, C-programs, counter machines But these are just Turing machines?

(20)

More “useful” undecidability?

Are only problems about Turing machines undecidable?

I Computers, C-programs, counter machines I Problems on CFLs: Given CFG G, isL(G) = Σ? I Problems on Tiling

(21)

More “useful” undecidability?

Are only problems about Turing machines undecidable?

I Computers, C-programs, counter machines I Problems on CFLs: Given CFG G, isL(G) = Σ? I Problems on Tiling

I Problems on String Matching

(22)

A simple programming exercise

A string matching problem

Given two lists A={s1, . . .sn}and B={t1, . . . ,tn}, over the same

alphabet, is there a sequence of combining elements that produces the same string in both lists?

I Does there exist a finite sequence 1≤i1, . . . ,im≤n such that si1. . .sim =ti1. . .tim

Consider the following lists

I A={110,0011,0110}and B={110110,00,110} 2, 3, 1! I A={0011,11,1101}andB ={101,011,110}

I A={100,0,1}andB ={1,100,0} Can you write an algorithm for solving this?

(23)

A simple programming exercise

A string matching problem

Given two lists A={s1, . . .sn}and B={t1, . . . ,tn}, over the same

alphabet, is there a sequence of combining elements that produces the same string in both lists?

I Does there exist a finite sequence 1≤i1, . . . ,im≤n such that si1. . .sim=ti1. . .tim

Consider the following lists

I A={110,0011,0110}and B={110110,00,110} 2, 3, 1! I A={0011,11,1101}andB ={101,011,110}

I A={100,0,1}andB ={1,100,0} Can you write an algorithm for solving this?

(24)

A simple programming exercise

A string matching problem

Given two lists A={s1, . . .sn}and B={t1, . . . ,tn}, over the same

alphabet, is there a sequence of combining elements that produces the same string in both lists?

I Does there exist a finite sequence 1≤i1, . . . ,im≤n such that si1. . .sim=ti1. . .tim

Consider the following lists

I A={110,0011,0110}and B={110110,00,110}

2, 3, 1! I A={0011,11,1101}andB ={101,011,110}

I A={100,0,1}andB ={1,100,0} Can you write an algorithm for solving this?

(25)

A simple programming exercise

A string matching problem

Given two lists A={s1, . . .sn}and B={t1, . . . ,tn}, over the same

alphabet, is there a sequence of combining elements that produces the same string in both lists?

I Does there exist a finite sequence 1≤i1, . . . ,im≤n such that si1. . .sim=ti1. . .tim

Consider the following lists

I A={110,0011,0110}and B={110110,00,110} 2, 3, 1!

I A={0011,11,1101}andB ={101,011,110} I A={100,0,1}andB ={1,100,0}

Can you write an algorithm for solving this?

(26)

A simple programming exercise

A string matching problem

Given two lists A={s1, . . .sn}and B={t1, . . . ,tn}, over the same

alphabet, is there a sequence of combining elements that produces the same string in both lists?

I Does there exist a finite sequence 1≤i1, . . . ,im≤n such that si1. . .sim=ti1. . .tim

Consider the following lists

I A={110,0011,0110}and B={110110,00,110} 2, 3, 1!

I A={0011,11,1101} andB ={101,011,110}

I A={100,0,1}andB ={1,100,0} Can you write an algorithm for solving this?

(27)

A simple programming exercise

A string matching problem

Given two lists A={s1, . . .sn}and B={t1, . . . ,tn}, over the same

alphabet, is there a sequence of combining elements that produces the same string in both lists?

I Does there exist a finite sequence 1≤i1, . . . ,im≤n such that si1. . .sim=ti1. . .tim

Consider the following lists

I A={110,0011,0110}and B={110110,00,110} 2, 3, 1!

I A={0011,11,1101} andB ={101,011,110}

Can you write an algorithm for solving this?

(28)

A simple programming exercise

A string matching problem

Given two lists A={s1, . . .sn}and B={t1, . . . ,tn}, over the same

alphabet, is there a sequence of combining elements that produces the same string in both lists?

I Does there exist a finite sequence 1≤i1, . . . ,im≤n such that si1. . .sim=ti1. . .tim

Consider the following lists

I A={110,0011,0110}and B={110110,00,110} 2, 3, 1!

I A={0011,11,1101} andB ={101,011,110}

I A={100,0,1}andB ={1,100,0}

References

Related documents

In general, we use the finite control to process the symbols that are being read on tape.. How does one

A language is decidable (or recursive) if there is a Turing machine accepting it, which has the additional property that it halts on all possible inputs... Variants of a Turing

A language is decidable (or recursive) if there is a Turing machine accepting it, which has the additional property that it halts on all possible inputs.. Every decidable language

Every Turing machine can be encoded as a string in {0, 1} ∗ I Just encode the description of the machine (in binary). I i.e., the 7-tuple: states, alphabet,

Thus it can be unfair to claim that the Newton’s method is faster than the gradient descent method on the grounds that it takes a fewer number of iterations to converge as compared

The difference between polynomial time and higher growth rates in running time is really the divide between what we can “solve” by computer and what in practice is not

Every Turing machine can be encoded as a string in {0, 1} ∗ Just encode the description of the machine (in binary).. Every string in {0, 1} ∗ is

– A whole range of formal models of computations (e.g. pushdown automata) between finite state machines and Turing machines with varying expressiveness and efficiency of