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