Publish on 27th October 2019
Category: Birds
0

CSE 105theory of computation

Fall 2019https://cseweb.ucsd.edu/classes/fa19/cse105-a/

Today's learning goalsSipser Ch 4.1, 4.2

Trace high-level descriptions of algorithms for computational problems.Use counting arguments to prove the existence of unrecognizable (undecidable) languages.Use diagonalization in a proof of undecidability.

Undecidable?

There are many ways to prove that a problemisdecidable.How do we find (and prove) that a problemis notdecidable?

Before we proved the Pumping Lemma …We proved there was a set that was not regular because

All sets of strings

Counting arguments

All RegularSets

Countable

Uncountable

All sets of strings

Counting arguments

All Turing-recognizable sets

Countable

Uncountable

Satisfied?

Maybe not …What's a specific example of a language that is not Turing-recognizable? or not Turing-decidable?Idea: consider a set that, were it to be Turing-decidable, would have to "talk" about itself, and contradict itself!

ATM

Recall ADFA= {<B,w> | B is a DFA and w is in L(B) }Decider for this set simulates arbitrary DFAATM= {<M,w> | M is a TM and w is in L(M) }Decider for this set simulates arbitrary TMs ???

ATM

ATM= {<M,w> | M is a TM and w is in L(M) }Define the TM N = "On input <M,w>:Simulate M on w.If M accepts, accept. If M rejects, reject."

ATM

ATM= {<M,w> | M is a TM and w is in L(M) }Define the TM N = "On input <M,w>:Simulate M on w.If M accepts, accept. If M rejects, reject."

What is L(N)?

ATM

ATM= {<M,w> | M is a TM and w is in L(M) }Define the TM N = "On input <M,w>:Simulate M on w.If M accepts, accept. If M rejects, reject."

Does N decide ATM?

ATM

ATM= {<M,w> | M is a TM and w is in L(M) }Define the TM N = "On input <M,w>:Simulate M on w.If M accepts, accept. If M rejects, reject."Conclude:ATMis Turing-recognizable.Is it decidable?

Diagonalization proof: ATMnot decidableSipser 4.11

Assume,towards a contradiction, that it is.CallMATMthe decider for ATM:For every TM M and every string w,Computation of MATMon <M,w> halts and accepts if w is in L(M).Computation of MATMon <M,w> halts and rejects if w is not in L(M).

Diagonalization proof: ATMnot decidableSipser 4.11

Assume, towards a contradiction, that MATMdecides ATMDefine the TM D = "On input <M>:Run MATMon <M, <M>>.If MATMaccepts, reject; if MATMrejects, accept."

Diagonalization proof: ATMnot decidableSipser 4.11

Assume, towards a contradiction, that MATMdecides ATMDefine the TM D = "On input <M>:Run MATMon <M, <M>>.If MATMaccepts, reject; if MATMrejects, accept."

Which of the following computations halt?Computation of D on <X>Computation of D on <Y> where Y is TM with L(Y) =Σ*Computation of D on <D>All of the above.

Diagonalization proof: ATMnot decidableSipser 4.11

Assume, towards a contradiction, that MATMdecides ATMDefine the TM D = "On input <M>:Run MATMon <M, <M>>.If MATMaccepts, reject; if MATMrejects, accept."Considerrunning D on input <D>. Because D is a decider:either computation halts and accepts…or computation halts and rejects…

Diagonalization proof: ATMnot decidableSipser 4.11

Assume, towards a contradiction, that MATMdecides ATMDefine the TM D = "On input <M>:Run MATMon <M, <M>>.If MATMaccepts, reject; if MATMrejects, accept."Considerrunning D on input <D>. Because D is a decider:either computation halts and accepts…or computation halts and rejects…

ATM

RecognizableNot decidableFact(from discussion section): A language is decidable iff it and its complement are both recgonizable.Corollary: The complement of ATMisunrecognizable.

Decidable vs. undecidable

So far

Do we have to diagonalize?

Next time: comparing difficulty of problems.

0

Embed

Upload

_-CSE 105 Theory of Computation - cseweb.ucsd.edu