Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30FORMAL LANGUAGES, AUTOMATA AND COMPUTABILITY15-453UNDECIDABILITY II: REDUCTIONSATM = { (M,w) | M is a TM that accepts string w }ATM is undecidable:(constructive proof & subtle) Assume machine H semi-decides ATMH( (M,w) ) =Accept if M accepts wRejects or loops otherwise Construct a new TM DH as follows: on input M, run H on (M,M) and output the “opposite” of H whenever possible.DH ( M ) =Reject if M accepts M(i.e. if H( M , M ) = Accept)Accept if M rejects M(i.e. if H( M , M ) = Reject)loops if M loops on M(i.e. if H( M , M ) loops)DHDHDHDHDHDHDHDHDHDHDHDHDHNote: There is no contradiction here! DH loops on DHWe can effectively construct an instance which does not belong to ATM (namely, (DH, DH) ) but H fails to tell us that.That is:Given any semi-decision machine H for ATM (and thus a potential decision machine for ATM ), we can effectively construct an instance which does not belong to ATM (namely, ( DH, DH )) but H fails to tell us that. So H cannot be a decision machine for ATMHALTTM = { (M,w) | M is a TM that halts on string w }Theorem: HALTTM is undecidableTHE HALTING PROBLEMProof: Assume, for a contradiction, that TM H decides HALTTMWe use H to construct a TM D that decides ATMOn input (M,w), D runs H on (M,w)If H rejects then rejectIf H accepts, run M on w until it halts:Accept if M accepts and Reject if M rejectsH(M,w)(M,w)MwIf M doesn’t halt: REJECTIf M haltsDoes M halt on w?DIn most cases, we will show that a language L is undecidable by showing that if it is decidable, then so is ATMWe reduce deciding ATM to deciding the language in questionATM “<” LSo, ATM “<” HaltTMIs HaltTM “<” ATM ?ETM = { M | M is a TM and L(M) =  }Theorem: ETM is undecidableProof: Assume, for a contradiction, that TM Z decides ETM sIf s  w, REJECTIf s = w, run M(w)Algorithm for deciding ATM:On input (M,w):Mw1. Create Mw2. Run Z on MwUse Z as a subroutine to decide ATMSo, L (Mw) =   M(w) does not acceptL (Mw)    M(w) acceptsAccepts if M does not accept wRejects, otherwiseZsIf s  w, REJECTIf s = w, run M(w)Mw(M,w)L(Mw) = ?So, L (Mw) =   M(w) does not acceptREVERSE accept/rejectDecision Machine for ATMNL(N) = ?MwREGULARTM = { M | M is a TM and L(M) is regular}Theorem: REGULARTM is undecidableProof: Assume, for a contradiction, that TM R decides REGULARTMRNIs L(N) regular?sIf s = 0n1n, acceptElse run M(w)MwL(Mw) = Σ* if M(w) accepts {0n1n } otherwiseL(Mw) is regular  M(w) acceptsMwIs L(Mw) regular?Yes  M accepts wALLPDA = { P | P is a PDA and L(P) = Σ* }Theorem: ALLPDA is undecidableProof: Assume, for a contradiction, that TM A decides ALLPDAWe use A to decide ATMMore subtle construction Idea! If M(w) does not accept, then there is no accepting computation for M on input w. Then any string of 0’s and 1’s will fail to be (a code for) an accepting computation. So, given (M, w) construct a PDA that accepts non-accepting computations of M on w. Thus, M(w) does not accept  L(P) = Σ* Idea!CONFIGURATIONS11010q700110q71 00 0 001 111COMPUTATION HISTORIESAn accepting computation history is a sequence of configurations C1,C2,…,Ck, whereAn rejecting computation history is a sequence of configurations C1,C2,…,Ck, where 1. C1 is the start configuration, 2. Ck is a rejecting configuration, 3. Each Ci follows from Ci-13. Each Ci follows from Ci-12. Ck is an accepting configuration,1. C1 is the start configuration,M accepts w if and only if there exists an accepting computation history that starts with C1=q0wALLPDA = { P | P is a PDA and L(P) = Σ* }Theorem: ALLPDA is undecidableProof: Assume, for a contradiction, that TM A decides ALLPDAWe use A to decide ATMOn input (M,w), construct a PDA P that accepts Σ* if and only if M does not accept w P will recognize all strings that are NOT accepting computation histories for M on w1. Do not start with C12. Do not end with an accepting configuration3. Where some Ci does not properly yield Ci+1P will recognize all strings (read as sequences of configurations) that:ε,ε → ε ε,ε → εε,ε → εNon-deterministic checks for 1, 2, and 3.P recognizes all strings except:#C1# C2R #C3 #C4R #C5 #C6R #….# CkIf k is odd, put Ck on stack and see if Ck+1R follows properly:For example, If =uaqibv and  (qi,b) = (qj,c,R), then Ck properly yields Ck+1  Ck+1 = uacqjvP recognizes all strings except:#C1# C2R #C3 #C4R #C5 #C6R #….# CkIf k is odd, put Ck on stack and see if Ck+1R follows properly:For example, If =uaqibv and  (qi,b) = (qj,c,L), then Ck properly yields Ck+1  Ck+1 = uqjacvP recognizes all strings except:#C1# C2R #C3 #C4R #C5 #C6R #….# CkIf k is even, put CkR on stack and see if Ck+1 follows properly:For example, If =uaqibv and  (qi,b) = (qj,c,L), then Ck properly yields Ck+1  Ck+1 = uqjacvALLPDA = { P | P is a PDA and L(P) = Σ* }Theorem: ALLPDA is undecidableProof: Assume, for a contradiction, that TM A decides ALLPDAWe use A to decide ATMOn input (M,w), construct a PDA P that accepts Σ* if and only if M does not accept w P will recognize all strings that are NOT accepting computation histories for M on wMAPPING REDUCIBILITYf : Σ*  Σ* is a computable function if some Turing machine M, on every input w, halts with just f(w) on its tapeA language A is mapping reducible to language B, written A m B, if there is a computable function (“coding”) f : Σ*  Σ*, where for every w,w  A  f(w)  Bf is called a reduction from A to BA BffTheorem: If A m B and B is decidable, then A is decidable Proof: Let M decide B and let f be a reduction from A to B We build a machine N that decides A as follows:On input w:1. Compute f(w)2. Run M on f(w)All undecidability proofs from today can be seen as constructing an f that reduces ATM to the proper languageExercise. Construct such an f in each case. (Hint. Sometimes you have to consider the complement of the language. )All undecidability proofs from today can be seen as constructing an f that reduces ATM to the proper languageATM m HALTTM :Map (M, w)  (M’, w) where M’(w) = M(w) if M(w) accepts loops otherwiseSo (M, w)  ATM  (M’, w)  HALTTMRead chapter 5.1-5.3 of the book for next