CS310 : Automata Theory 2019

(1)

cbna CS310 : Automata Theory 2019 Instructor: S. Akshay IITB, India 1

CS310 : Automata Theory 2019

Lecture 30: Rice theorem

Instructor: S. Akshay

IITB, India

19-03-2019

(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

Regular (Decidable (Recursively Enumerable( All languages DFA/NFA <Algorithms/Halting TM<Semi-algorithms/TM

(3)

Recap

5. Undecidability and a proof technique by diagonalization

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

(4)

Recap

(5)

Recap

7. Today: Rice’s theorem

(6)

Rice’s theorem

Rice’s theorem (1953)

Any non-trivial property of R.E languages is undecidable!

I Property P ≡set of languages satisfyingP

I Property of r.e languages: membership of M in P depends only on the language of M. If L(M) =L(M⁰), then hMi ∈P iff hM⁰i ∈P.

I Non-trivial: It holds for some but not all TMs.

(7)

Rice’s theorem

I Property of r.e languages: membership of M in P depends only on the language of M. If L(M) =L(M⁰), then hMi ∈P iff hM⁰i ∈P.

(8)

Rice’s theorem

I Property of r.e languages: membership of M in P depends only on the language ofM. If L(M) =L(M⁰), then hMi ∈P iff hM⁰i ∈P.

(9)

Rice’s theorem

I Property of r.e languages: membership of M in P depends only on the language ofM. If L(M) =L(M⁰), then hMi ∈P iff hM⁰i ∈P.

(10)

Property: set of languages

Property of r.e. languages

Just a subset of r.e. languages. Thus, Lsatisfies a property P iff L∈P.

Examples:

I Set of regular languages I Set of context-free languages I Set of all languages

I {∅} I ∅

Given a property P, denote L_P ={hMi |L(M)∈P} So decidability of propertyP is decidability of language L_P.

(11)

Property: set of languages

Just a subset of r.e. languages. Thus, Lsatisfies a property P iff L∈P. Examples:

I Set of regular languages I Set of context-free languages

I Set of all languages I {∅}

I ∅

(12)

Property: set of languages

I {∅} I ∅

(13)

Property: set of languages

I {∅}

I ∅

(14)

Property: set of languages

I {∅}

I ∅

Given a property P, denote L_P ={hMi |L(M)∈P}

So decidability of property P is decidability of language L_P.

(15)

Non-trivial property

For a property P,L_P ={hMi |L(M)∈P}.

A property P of r.e. languages is called non-trivialif I L_P 6=∅, i.e., there exists TM M,L(M)∈P.

I L_P 6= all r.e. languages, i.e., there exists TM M,L(M)6∈P.

Examples

I {hMi |L(M) is regular } I L_P ={hMi |L(M) =∅}

I L_p={hMi |M is a TM s.t. L(M) is accepted by a TM with even number of states }.

(16)

Non-trivial property

For a property P,L_P ={hMi |L(M)∈P}.

A property P of r.e. languages is called non-trivialif I L_P 6=∅, i.e., there exists TM M,L(M)∈P.

I L_P 6= all r.e. languages, i.e., there exists TM M,L(M)6∈P.

Examples

I {hMi |L(M) is regular } I L_P ={hMi |L(M) =∅}

I L_p ={hMi |M is a TM s.t. L(M) is accepted by a TM with even number of states }.

(17)

Rice’s Theorem

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

Remark: (when not to apply Rice’s theorem)

1. Property is is about TMs and not their languages: e.g., TM has at least 10 states.

2. Cannot show non- Turing recognizability, only undecidability.

(18)

Rice’s Theorem

(19)

Rice’s Theorem

(20)

Can you apply Rice’s theorem?

For the following, answer if Rice’s theorem is applicable 1. {hMi |M runs for 5 steps on word 010}.

2. {hMi |L(M) is recognized by a TM with at least 25 states.}.

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

4. {hMi |M has at most 25 states.}.

5. {hMi |L(M) is finite.}.

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

I For each of No answers above, is the language decidable?

I What do you do when Rice’s theorem does not apply? Fall back on reductions!

(21)

Can you apply Rice’s theorem?

For the following, answer if Rice’s theorem is applicable

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

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

3. {hMi |L(M) is recognized by a TM with at most 25 states.}. Yes, if tape alphabet is fixed, else no!

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

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

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

I For each of No answers above, is the language decidable?

I What do you do when Rice’s theorem does not apply? Fall back on reductions!

(22)

Proof idea

Rice’s Theorem

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

I Assume L_P is decidable, we will show thatATM is decidable. I Since P is non-trivial, ∃L,M_L with property P.

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

I TakehM,wias i/p, and o/phM⁰i, s.tL(M⁰)∈P iffM acc w. I M⁰ is the foll:

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

I ThusM⁰ either acc∅ orLdepending on ifM accw. I This gives an algo forATM so completes the proof.

(23)

Proof idea

Rice’s Theorem

I Let P be a non-trivial property of r.e, such that∅ 6∈P. I Assume L_P is decidable, we will show thatATM is decidable.

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

(24)

Proof idea

Rice’s Theorem

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

(25)

Proof idea

Rice’s Theorem

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

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

(26)

Proof idea

Rice’s Theorem

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

(27)

Proof idea

Rice’s Theorem

I TakehM,wias i/p, and o/phM⁰i, s.tL(M⁰)∈P iffM acc w.

I M⁰ is the foll:

(28)

Proof idea

Rice’s Theorem

I M⁰ is the foll:

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

2. if acc, then simulateMLonx, acc iffMLaccx.

(29)

Proof idea

Rice’s Theorem

I M⁰ is the foll:

I ThusM⁰ either acc∅ orLdepending on ifM accw.

I This gives an algo forATM so completes the proof.

(30)

Proof idea

Rice’s Theorem

I M⁰ is the foll:

(31)

Proof idea

I But what ifP has∅ in it!?

I Take P. I Now ∅ 6∈P.

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

(32)

Proof idea

(33)