DecidabilityExamples of decidable languagesThe acceptance problem for DFAs is decidableThe acceptance problem for NFAs is decidableThe emptiness problem for the language of a DFA is decidableThe universal Turing machineATM is undecidableSlide 8A Turing-unrecognizable languageThe language hierarchy summaryDecidabilityDecidabilityChapter 4 Giorgi Japaridze Theory of ComputabilityExamples of decidable languages4.1.aGiorgi Japaridze Theory of ComputabilityDecidable:•{1,3,5}• •{x | x is even}•{x | x is a perfect square}•{x | x2-10x = 0}•{x | x=y*z for some integers y,z>1 (i.e. x is not prime)}•{x | x is a prime (i.e. x is not divisible by anything except 1 and itself)}•{<G> | G is a connected graph}•{<P> | P is a one-variable polynomial expression with an integral root} Undecidable:•{<P> | P is a two-variable polynomial expression with an integral root}The acceptance problem for DFAs is decidable4.1.bGiorgi Japaridze Theory of ComputabilityTheorem 4.1: ADFA is a decidable language.Let ADFA = {<B,w> | B is a DFA that accepts input string w}Proof idea: Here is a Turing machine M that decides ADFA:M = “On input <B,w>, where B is a DFA and w is a string: 1. Simulate B on input w. 2. If the simulation ends in an accept state, accept. If the simulation ends in a nonaccept state, reject.”The acceptance problem for NFAs is decidable4.1.cGiorgi Japaridze Theory of ComputabilityTheorem 4.2: ANFA is a decidable language.Let ANFA = {<B,w> | B is an NFA that accepts input string w}Proof idea: Here is a Turing machine N that decides ANFA:N = “On input <B,w>, where B is an NFA and w is a string: 1. Convert NFA B to an equivalent DFA C using the procedure for this conversion that we learned. 2. Run TM M from Theorem 4.1 on input <C,w>. 3. If M accepts, accept. If M rejects, reject.”The emptiness problem for the language of a DFA is decidable4.1.dGiorgi Japaridze Theory of ComputabilityTheorem 4.4: EDFA is a decidable language.Let EDFA = {<A> | A is a DFA and L(A)=}Proof idea: Here is a Turing machine T that decides EDFA:T = “On input <A>, where A is a DFA: 1. Mark the start state of A. 2. Repeat until no new states get marked: 3. Mark any state that has a transition coming into it from any state that is already marked. 4. If no accept state is marked, accept; otherwise reject.”The universal Turing machine4.2.aGiorgi Japaridze Theory of ComputabilityTheorem: ATM is Turing-recognizable. Proof idea. The following TM U, called the universal TM, recognizes ATM:U = “On input <M,w>, where M is a TM and w is a string: 1. Simulate M on input w. 2. If M ever enters its accept state, accept; if M ever enters its reject state, reject.”Does U also decide ATM?Let ATM = {<M,w> | M is a TM and M accepts string w}ATM is misleadingly called the halting problem in the textbook.Instead, we will call it the acceptance problem.ATM is undecidable4.2.b.1Giorgi Japaridze Theory of ComputabilityTheorem 4.11: ATM is undecidable.Proof idea. Suppose, for a contradiction, that ATM is decidable.That is, there is a TM H that decides ATM. Thus, that machine H behaves as follows: accept if M accepts w reject if M does not accept wH(<M,w>) =Using H as a subroutine, we can construct the following TM D:D = “On input <M>, where M is a TM: 1. Run H on input <M,<M>>. 2. Do the opposite of what H does. That is, if H accepts, reject, and if H rejects, accept.”Thus, D(<M>) =accept if M does not accept <M>reject if M accepts <M>ATM is undecidable4.2.b.2Giorgi Japaridze Theory of ComputabilityBut then D(<D>) =accept if D does not accept <D>reject if D accepts <D>Contradiction!To summarize:•H accepts <M,w> exactly when M accepts w.•D rejects <M> exactly when M accepts M.•D rejects <D> exactly when D accepts <D>.A Turing-unrecognizable language4.2.cGiorgi Japaridze Theory of ComputabilityATM = {<M,w> | M is a TM and M accepts string w}ATM = {<M,w> | M is a TM and M does not accept string w}Proof idea. Suppose, for a contradiction, that ATM is Turing-recognizable.That is, there is a TM U that recognizes ATM. • U recognizes ATM (slide 4.2.a)• U recognizes ATM Thus,Let M = “On input w: 1. Run both U and U on input w in parallel; 2. If U accepts, accept; if U accepts, reject.”It can bee seen that M decides ATM, which contradicts Theorem 4.11. Theorem 4.23: ATM is Turing-unrecognizable.The language hierarchy summary4.2.dGiorgi Japaridze Theory of ComputabilityRegular languagesContext-free languages{anbn | n0} {anbncn | n0}Turing-recognizable languagesATMAll languagesTuring-decidable