Question? Leave a message!




Decidable/Undecidable problems

Decidable/Undecidable problems
Dr.SamuelHunt Profile Pic
Dr.SamuelHunt,United Arab Emirates,Teacher
Published Date:21-07-2017
Website URL
Comment
Decidability Decidable/Undecidable problemsAccepting: Definition • Let T = (Q, , , , s) be a TM. • T accepts a string w in  if (s,w) - (h, 1) . T • T accepts a language L if, for any string w in L, T accepts w. www.ThesisScientist.comCharacteristic function • For any language L , the characteristic function of L is the function  (x) such that L – (x) = 1 if x  L L – (x) = 0 otherwise L • Example Let L =  0,1 n () n () 2n () , where n () is the 1 0 1 x number of x’s in . – () = 1 if n () n () 2n () L 1 0 1 – () = 0 otherwise L www.ThesisScientist.comDeciding: Definition • Let T = (Q, , , , s) be a TM. • T decides a language L if T computes the characteristic function of L. • T decides a language L if – for any string w in L, T halts on w with output 1, – for any string w inL, T halts on w with output 0. www.ThesisScientist.com/,R /1,L 0/,R/,L /,R Accepting/Deciding: Example S n n n n T TM M d ae cce ciding ptining g L = L= 00 10 10nn00 0/,L /,L 1/,L Hang when /,L 2n input = 0 /,L 1/,R p1 q1 r1 Hang when input n n+m = 0 1 … 0 0/0,L 1/1,L 0/0,R If the input x is in L, 1/1,R r2 p4 p2 q2 T halts with output 1. If the input x is not in L, T hangs. 1/,L Hang when input h /,L p3 h n+m n = 0 …0 www.ThesisScientist.com /0,L /,RRecursively enumerable languages • A language L is recursively enumerable if there is a Turing machine T accepting L. • A language L is Turing-acceptable if there is a Turing machine T accepting L. • Example: n n 0 10 n0 is a recursively-enumerable language. www.ThesisScientist.comRecursive languages • A language L is recursive if there is a Turing machine T deciding L. • A language L is Turing-decidable if there is a Turing machine T deciding L. • Example: n n 0 10 n0 is a recursive language. www.ThesisScientist.comClosure Properties of the Class of Recursive LanguagesClosure Property Under Complementation Theorem: Let L be a recursive language over . Then,L is recursive. Proof: Let L be a recursive language over . Then, there exists a TM T computing  . L Construct a tape TM M computing  . as follows: L 0  T T T moveRight write1 1 T write0 Then,L is recursive. www.ThesisScientist.comClosure Property Under Union Theorem: Let L and L be recursive languages over 1 2 . Then, LL is recursive. 1 2 Proof: Let L and L be recursive languages over . 1 2 Then, there exist TM’s T and T computing  and 1 2 L1  , respectively. L2 Construct a 2-tape TM M as follows: 0  T T T T T copyTape1ToTape2 1 moveRight copyTape2ToTape1 2 1 www.ThesisScientist.comClosure Property Under Union 0  T T T T T copyTape1ToTape2 1 moveRight copyTape2ToTape1 2 1 If the input w is not in L and L ,  (w) and  (w)=0. 1 2 L1 L2 Thus, both T and T must run, and M halts with 1 2 output 0. If the input w is in L ,  (w)=1. Thus, M halts with 1 L1 output 1. If the input w is not in L but is in L ,  (w)=0 and 1 2 L1  (w)=1. Thus, M halts with output 1. L2 That is, M computes characteristic function of  . L Then, LL is recursive. 1 2 www.ThesisScientist.comClosure Property Under Intersection Theorem: Let L and L be recursive languages over 1 2 . Then, LL is recursive. 1 2 Proof: Let L and L be recursive languages over . 1 2 Then, there exist TM’s T and T computing  and 1 2 L1  , respectively. L2 Construct a 2-tape TM M as follows: 1  T T T T T copyTape1ToTape2 1 moveRight copyTape2ToTape1 2 0 www.ThesisScientist.comClosure Property Under Intersection 1  T T T T T copyTape1ToTape2 1 moveRight copyTape2ToTape1 2 0 If the input w is in LL ,  (w) and  (w)=1. Thus, M halts 1 2 L1 L2 with output 1. If the input w is not in L ,  (w)=0. Thus, M halts with output 0. 1 L1 If the input w is in L but is not in L ,  (w)=1 and  (w)=0. 1 2 L1 L2 Thus, M halts with output 0. That is, M computes characteristic function of  . L1L2 Then, LL is recursive. 1 2 www.ThesisScientist.comClosure Properties of the Class of Recursively Enumerable LanguagesClosure Property Under Union Theorem: Let L and L be recursively enumerable 1 2 languages over . Then, LL is also recursively 1 2 enumerable. Proof: Let L and L be recursively enumerable languages 1 2 over . Then, there exist TM’s T and T accepting L and L , 1 2 1 2 respectively. S T 1 Construct an NTM M as follows. T 2 www.ThesisScientist.comClosure Property Under Union S T 1 T 2 If w is in L , but not in L , then T in M runs and halts. 1 2 1 If w is in not L , but in L , then T in M runs and halts. 1 2 2 If w is in both L and L , then either T or T runs and halts. 1 2 1 2 For these 3 cases, M halts. If w is neither in L nor in L , then either T or T runs 1 2 1 2 but both never halt. Then, M does not halt. Thus, M accepts LL . That is, LL is recursively 1 2 1 2 enumerable. www.ThesisScientist.comClosure Property Under Intersection Theorem: Let L and L be recursively enumerable 1 2 languages over . Then, LL is also recursively 1 2 enumerable. Proof: Let L and L be recursively enumerable languages 1 2 over . Then, there exist TM’s T and T accepting L and L , 1 2 1 2 respectively. Construct an NTM M as follows. 1  T T T T T copyTape1ToTape2 1 moveRight copyTape2ToTape1 2 www.ThesisScientist.comClosure Property Under Intersection 1  T T T T T copyTape1ToTape2 1 moveRight copyTape2ToTape1 2 If w is in not L , then T in M does not halt. Then, M does 1 1 not halt. If w is in L , but not in L , then T in M halts and T can 1 2 1 2 finally start, but does not halt. Then, M does not halt. If w is in both L and L , then T in M halts and T can 1 2 1 2 finally start, and finally halt. Then, M halts. Thus, M accepts LL . That is, LL is recursively 1 2 1 2 enumerable. www.ThesisScientist.comClosure Property Under Union (II) Theorem: Let L and L be recursively enumerable 1 2 languages over . Then, LL is also recursively 1 2 enumerable. Proof: Let L and L be recursively enumerable languages over 1 2 . Then, there exist DTM’s T =(Q , , ,  , s ) and T =(Q , 1 1 1 1 2 2 , ,  , s ) accepting L and L , respectively. 2 2 1 2 Construct a 2-tape TM M which simulates T and T 1 2 simultaneously. Tape 1 represents T ’s tape and Tape 1 2 represents T ’s tape. www.ThesisScientist.com 2Closure Property Under Union (II) Let M = (QQ , , , , (s ,s )) where 1 2 1 2 –((p ,p ),a ,a ) = ((q ,q ),b ,b ,d ,d ) for 1 2 1 2 1 2 1 2 1 2  (p ,a )=(q ,b ,d ) and  (p ,a )=(q ,b ,d ) 1 1 1 1 1 1 2 2 2 2 2 2 –((p ,p ),a ,a ) = (h,b ,b ,d ,d ) for  (p ,a )=(h,b ,d ) 1 2 1 2 1 2 1 2 1 1 1 1 1 or  (p ,a )=(h,b ,d ) 2 2 2 2 2 If either T or T halt, M finally gets to the state h. 1 2 If neither T nor T halt, M never gets to the state h. 1 2 www.ThesisScientist.com