CS310 : Automata Theory 2019

(1)

CS310 : Automata Theory 2019

Lecture 29: Reductions contd.

Instructor: S. Akshay

IITB, India

18-03-2019

(2)

Pop-Quiz

Which is easier: Emptiness or non-emptiness?

I L_e ={hMi |L(M) =∅}

I Lne ={hMi |L(M)6=∅}

(3)

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

(4)

Recap

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

5. Undecidability and a proof technique by diagonalization

I A universal TM langL^A_TM ={hM,wi |M is a TM andM acceptsw}

(5)

Recap

I A universal TM langL^A_TM ={hM,wi |M is a TM andM acceptsw}

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

(6)

Recap

I A universal TM langL^A_TM ={hM,wi |M is a TM andM acceptsw} 6. Reductions.

(7)

Recap

I A universal TM langL^A_TM ={hM,wi |M is a TM andM acceptsw} 6. Reductions.

7. Today:

Reductions and moar undecidability!

(8)

The principle of reduction

(Many-to-one) Reduction

I An algorithm (halting TM!) to convert instances of a problemP1 to anotherP2 such that,

I answer is yes forP1 iff answer is yes forP2

I answer is no forP1iff answer is no forP2

Note that every instance of P2 need not be covered!

Theorem: If there is a reduction fromP₁ to P₂, (thenP2 is at least as hard as P1, i.e.,)

I if P₁ is undecidable, then so isP₂ I if P₁ is not r.e., then so isP₂.

(9)

The principle of reduction

Theorem: If there is a reduction from P₁ to P₂, (then P2 is at least as hard asP1, i.e.,)

I if P₁ is undecidable, then so isP₂ I if P₁ is not r.e., then so isP₂.

(10)

The principle of reduction

I if P1 is undecidable, then so isP2

I if P₁ is not r.e., then so isP₂.

(11)

The principle of reduction

I if P1 is undecidable, then so isP2

I if P₁ is not r.e., then so isP₂.

(12)

The halting problem

The halting problem for Turing Machines is undecidable Does a given Turing machine halt on a given input?

I L^HALT_TM ={hM,wi |M is a TM andM halts on inputw}.

Proof: Suppose there exists TMH deciding L^HALT_TM , then construct a TMD s.t., on inputhM,wi:

I runs TMH on inputhM,wi I if H rejects then reject.

I if H accepts, then simulate M onw until it halts. I if at halting M has acceptedw, accept, else reject. ButD decidesL^A_TM which is undecidable. A contradiction. This proof strategy is called a reduction.

(13)

The halting problem

Proof: Suppose there exists TM H decidingL^HALT_TM , then construct a TMD s.t., on inputhM,wi:

I if H accepts, then simulate M onw until it halts.

I if at halting M has acceptedw, accept, else reject.

But D decidesL^A_TM which is undecidable. A contradiction.

This proof strategy is called a reduction.

(14)

The halting problem

Proof: Suppose there exists TM H decidingL^HALT_TM , then construct a TMD s.t., on inputhM,wi:

I if H accepts, then simulate M onw until it halts.

I if at halting M has acceptedw, accept, else reject.

But D decidesL^A_TM which is undecidable. A contradiction.

This proof strategy is called a reduction.

(15)

Reduction from the acceptance problem

hM,wi H

M Acc w

Rej Rej

Rej Rej Acc Acc

(16)

Some more undecidable problems

The emptiness problem for TMs

Does a given Turing machine accept any word?

I L^∅_TM ={hMi |M is a TM andL(M) =∅}.

Proof:

I For contradiction, assume its decidable, say by TM R. I DefineM₁ which on input x,

I ifx6=w, it rejects

I ifx=w, runM onw and accept ifM accepts. I ConstructS which decidesATM: Given inputhM,wi,

I ConstructM1on tape fromM andw, I RunR on inputhM1i.

I IfR accepts,reject; ifR rejects thenaccept.

(17)

Some more undecidable problems

The emptiness problem for TMs is undecidable Does a given Turing machine accept any word?

Proof:

I For contradiction, assume its decidable, say by TM R.

I DefineM₁ which on input x, I ifx6=w, it rejects

I ifx=w, runM onw and accept ifM accepts. I ConstructS which decidesATM: Given inputhM,wi,

(18)

Some more undecidable problems

Proof:

I ifx=w, runM onw and accept ifM accepts.

I ConstructS which decidesATM: Given inputhM,wi, I ConstructM1on tape fromM andw,

I RunR on inputhM1i.

(19)

Some more undecidable problems

Proof:

I ConstructS which decidesATM: Given inputhM,wi,

(20)

Some more undecidable problems

Proof:

(21)

Some more undecidable problems

Proof:

(22)

Some more undecidable problems

Proof:

I IfRaccepts,

reject; ifR rejects thenaccept.

(23)

Some more undecidable problems

Proof:

I IfRaccepts, reject; ifR rejects thenaccept.

(24)

Some more undecidable problems

The regularity problem for TMs

Does a given Turing machine accept a regular language?

I L^REG_TM ={hMi |M is a TM andL(M) is a regular language}.

Proof: By contradiction, assumeR decides Reg. We define S I S = On input hM,wi;

I construct TMM2as follows: M2on input x does the foll:

I ifx has the form 0ⁿ1ⁿ, accept.

I If not, runM onw and accept ifM acceptsw. I RunR onhM2i.

I IfR accepts,accept; ifR rejects,reject.

(25)

Some more undecidable problems

Proof: By contradiction, assume R decides Reg. We define S

I S = On input hM,wi;

I construct TMM2as follows: M2on input x does the foll:

(26)

Some more undecidable problems

Proof: By contradiction, assume R decides Reg. We define S I S = On input hM,wi;

I construct TMM2as follows:

M2on input x does the foll: I ifx has the form 0ⁿ1ⁿ, accept.

(27)

Some more undecidable problems

M₂on input x does the foll:

I If not, runM onw and accept ifM acceptsw.

I RunR onhM2i.

(28)

Some more undecidable problems

(29)

Some more undecidable problems

I IfRaccepts, accept; ifR rejects,reject.

(30)

Some more undecidable problems

I L^EQ_TM ={hM₁,M₂i |M are TMs andL(M₁) =L(M₂)}.

Proof: Reduce to emptiness.

(31)

Some more undecidable problems

I L^EQ_TM ={hM₁,M₂i |M are TMs andL(M₁) =L(M₂)}.

Proof: Reduce to emptiness.

(32)

Which is easier: Emptiness or non-emptiness?

I L_e ={hMi |L(M) =∅}

I Lne ={hMi |L(M)6=∅}

(33)

Is everything about Turing machines undecidable?

1. {hMi |L(M) =∅}

2. {hMi |L(M) is regular } 3. {hMi |L(M) is context-free} 4. {hMi |L(M) is finite } 5. {hMi |M has 5 states} 6. {hMi |L(M) is a language }

7. {hMi |M makes at least 5 moves on some input} Rice’s Theorem

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

(34)

Is everything about Turing machines undecidable?

1. {hMi |L(M) =∅}

2. {hMi |L(M) is regular }

3. {hMi |L(M) is context-free} 4. {hMi |L(M) is finite } 5. {hMi |M has 5 states} 6. {hMi |L(M) is a language }

(35)

Is everything about Turing machines undecidable?

1. {hMi |L(M) =∅}

2. {hMi |L(M) is regular } 3. {hMi |L(M) is context-free}

4. {hMi |L(M) is finite } 5. {hMi |M has 5 states} 6. {hMi |L(M) is a language }

(36)

Is everything about Turing machines undecidable?

1. {hMi |L(M) =∅}

2. {hMi |L(M) is regular } 3. {hMi |L(M) is context-free} 4. {hMi |L(M) is finite}

5. {hMi |M has 5 states} 6. {hMi |L(M) is a language }

(37)

Is everything about Turing machines undecidable?

1. {hMi |L(M) =∅}

2. {hMi |L(M) is regular } 3. {hMi |L(M) is context-free} 4. {hMi |L(M) is finite} 5. {hMi |M has 5 states }

6. {hMi |L(M) is a language }

(38)

Is everything about Turing machines undecidable?

1. {hMi |L(M) =∅}

2. {hMi |L(M) is regular } 3. {hMi |L(M) is context-free} 4. {hMi |L(M) is finite} 5. {hMi |M has 5 states } 6. {hMi |L(M) is a language }

(39)

Is everything about Turing machines undecidable?

1. {hMi |L(M) =∅}

7. {hMi |M makes at least 5 moves on some input}

Rice’s Theorem

(40)

Is everything about Turing machines undecidable?

1. {hMi |L(M) =∅}

Rice’s Theorem

(41)

Is everything about Turing machines undecidable?

1. {hMi |L(M) =∅}

Rice’s Theorem

(42)

Rice’s theorem

Rice’s theorem (1953)

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

I Property P ≡set of languages (i.e., their TM encodings) satisfyingP 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. I Non-trivial: It holds for some but not all TMs.