Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52FORMAL LANGUAGES, AUTOMATA AND COMPUTABILITY15-453ATM = { (M,w) | M is a TM that accepts string w }HALTTM = { (M,w) | M is a TM that halts on string w }ETM = { M | M is a TM and L(M) =  }REGTM = { M | M is a TM and L(M) is regular}ALLPDA = { P | P is a PDA and L(P) = Σ* }EQTM = {( M, N) | M, N are TMs and L(M) =L(N)}ALL UNDECIDABLEUse Reductions to ProveWhich are SEMI-DECIDABLE?ABffLet f : Σ*  Σ* be a computable function such that w  A  f(w)  BSay: A is mapping reducible to B; Write: A m B Σ*Σ*Also,  A m  B, why?Theorem: If A m B and B is (semi) decidable, then A is (semi) 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)CLAIM: ATM m HALTTMf: (M,w)  (M’, w) where M’( w) = M(w) if M(w) accepts Loops otherwiseSo, (M, w ) ATM  (M’, w)  HALTTMATM = { (M,w) | M is a TM that accepts string w }HALTTM = { (M,w) | M is a TM that halts on string w }CONSTRUCT f : Σ*  Σ* So HALTTM is NOT DECIDABLE, but it is SEMI-DECIDABLE (Why?)CLAIM: ATM m  ETMf: (M,w)  Mw where Mw (s) = M(w) if s = w Loops otherwiseSo, (M, w ) ATM  Mw   ETMATM = { (M,w) | M is a TM that accepts string w }ETM = { M | M is a TM and L(M) =  }CONSTRUCT f : Σ*  Σ* So, M(w) accepts  L (Mw)   ATM m ETMSo  ETM is NOT DECIDABLE, but it is SEMI-DECIDABLE (why?)Is ETM SEMI-DECIDABLE?CLAIM: ATM m REGTMf: (M,w)  M’w where M’w (s) = accept if s = 0n1n M(w) otherwiseSo, (M, w ) ATM  M’w  REGTM ATM = { (M,w) | M is a TM that accepts string w }REGTM = { M | M is a TM and L(M) is regular}CONSTRUCT f : Σ*  Σ* So, L (M’w) = Σ* if M(w) accepts {0n1n} if notSo REGTM is UNDECIDABLEIs REG SEMI-DECIDABLE?CLAIM:  ATM m REGTMf: (M,w)  M”w where M”w (s) = accept if s = 0n1n and M(w) accepts Loop otherwiseSo, (M, w )  ATM  M”w  REGTM ATM = { (M,w) | M is a TM that accepts string w }REGTM = { M | M is a TM and L(M) is regular}CONSTRUCT f : Σ*  Σ* So, L (M’w) = {0n1n} if M(w) accepts  if notSo, REG NOT SEMI-DECIDABLE So, REG NOT SEMI-DECIDABLECLAIM: ETM m EQTMf: M  (M, M  ) where M  (s) = LoopsSo, M E TM  (M, M  )  EQTM ETM = { M | M is a TM and L(M) =  }EQTM = {( M, N) | M, N are TMs and L(M) =L(N)}CONSTRUCT f : Σ*  Σ* So EQTM is UNDECIDABLEIs EQTM SEMI-DECIDABLE?NO, since,  ATM m ETM m EQTMCLAIM: ATM m  ALLPDAf: (M,w)  Pw where Pw (s) = accept iff s is NOT an accepting computation of M(w)So, (M, w )  ATM  Pw  ALLPDA ATM = { (M,w) | M is a TM that accepts string w }ALLPDA = { P | P is a PDA and L(P) = Σ* }CONSTRUCT f : Σ*  Σ*  ATM m ALLPDASo, (M, w ) ATM  Pw   ALLPDACOMPUTATION 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=q0w1. 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.0 → , R → , Rqacceptqreject0 → x, Rx → x, R → , Rx → x, R0 → 0, Lx → x, Lx → x, R → , L → , R0 → x, R0 → 0, R → , Rx → x, R{ 0 | n ≥ 0 }2nq0q1q2q3q40 → , R → , Rqacceptqreject0 → x, Rx → x, R → , Rx → x, R0 → 0, Lx → x, Lx → x, R → , L → , R0 → x, R0 → 0, R → , Rx → x, R{ 0 | n ≥ 0 }2nq0q1q2q3q4q00000q1000xq300x0q40x0xq3x0q2xxq20xq2x0xq2x0xP 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: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.q00000q1000xq300x0q40x0xq3x0q2xxq20xq2x0x#q00000#000q1#xq300#0q40x #x0xq3# ... #0 0 0 q10000q0ODD:q00000q1000xq300x0q40x0xq3x0q2xxq20xq2x0x#q00000#000q1#xq300#0q40x #x0xq3# ... #0 0 0 q10000q0ODD:q00000q1000xq300x0q40x0xq3x0q2xxq20xq2x0x#q00000#000q1#xq300#0q40x #x0xq3# ... #0 0 0 q10000q0ODD:q00000q1000xq300x0q40x0xq3x0q2xxq20xq2x0x#q00000#000q1#xq300#0q40x #x0xq3# ... #x q30 0q1000EVEN:q00000q1000xq300x0q40x0xq3x0q2xxq20xq2x0x#q00000#000q1#xq300#0q40x #x0xq3# ... #q1000EVENx q30 0:THE POST CORRESPONDENCE PROBLEMTHE PCP GAMEbaaaabbbcbbabaaaabaaaaaaaacaaacaaaaaaaaaabcaabcaaababccaabbcacaaabcccaaacccaabcabGENERAL RULE #1If every top string is longer than the corresponding bottom one, there can’t be a matchaabaaaccabbcacaaabbGENERAL RULE #2If there is a domino with the same string on the top and on the bottom, there is a matchPOST CORRESPONDENCE PROBLEMGiven a collection of dominos, is there a match?PCP = { P | P is a set of dominos with a match }PCP is undecidable!THE FPCP GAME… is just like the PCP game except that a match has to start with the first dominoaaaaaaaacaaacaaaaaaaaFPCPbaaaabbbcbbaFPCPTheorem: FPCP is undecidableProof: Assume machine C decides FPCPWe will show how to use C to decide ATMP has a