Question? Leave a message!




Decidable/Undecidable problems

Decidable/Undecidable problems
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 Turingacceptable if there is a Turing machine T accepting L. • Example: n n 0 10 n0 is a recursivelyenumerable language. www.ThesisScientist.comRecursive languages • A language L is recursive if there is a Turing machine T deciding L. • A language L is Turingdecidable 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 2tape 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 2tape 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 2tape 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.comClosure Property Under Intersection (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 2tape TM M which simulates T and T 1 2 simultaneously. Tape 1 represents T ’s tape and Tape 1 2 represents T ’s tape. 2 www.ThesisScientist.comClosure Property Under Intersection (II) Let M = ((Qh)(Qh), , , , (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 –((h,p ),a ,a ) = ((h,q ),a ,b ,S,d ) for all p ,a ,a and 2 1 2 2 1 2 2 2 1 2  (p ,a )=(q ,b ,d ) 2 2 2 2 2 2 –((p ,h),a ,a ) = ((q ,h),b ,a ,d ,S) for all p ,a ,a and 1 1 2 1 1 2 1 1 1 2  (p ,a )=(q ,b ,d ) 1 1 1 1 1 1 –((h,h),a ,a ) = (h,a ,a ,S,S) for all a ,a 1 2 1 2 1 2 If neither T1 nor T2 halt, M never gets to the state h. If T halts and T does not halt, M gets to the state (h,p). 1 2 If T halts and T does not halt, M gets to the state (p,h). 2 1 If both T and T halt, M finally gets to the state h. 1 2 www.ThesisScientist.comRelationship Between the Classes of Recursively Enumerable and Recursive LanguagesRelationship between RE and Recursive Languages Theorem: If L is a recursive language, then L is recursively enumerable. Proof: Let L be a recursive language over . Then, there is a TM T deciding L. Then, T also accepts L. Thus, L is recursively enumerable. www.ThesisScientist.comRelationship between RE and Recursive Languages Theorem: Let L be a language. If L andL are recursively enumerable, then L is recursive. Proof: Let L andL be recursivelyenumerable languages over . Then, there are a TM T accepting L, and a TMT acceptingL. For any string w in  , w is either in L or inL. That is, either T orT must halt on w, for any w in  . We construct an NTM M as follows: accept S T If w is in L, T halts on w and thus, M accepts w. reject T If w is not in L,T halts on w and thus, M rejects w. Then, M computes the characteristic function of L. Then, L is recursive. www.ThesisScientist.comDecision Problems • A decision problem is a prob. whose ans. is either yes or no • A yesinstance (or noinstance) of a problem P is the instance of P whose answer is yes (or no, respectively) • A decision problem P can be encoded by f over  e as a language f (X) X is a yesinstance of P. e www.ThesisScientist.comEncoding of decision problems • Is X a prime X 1 X is a prime • Does TM T accept string e(T) e(T) T is a TM accepting string e(T) • Does TM T accept string w e(T)e(w) T is a TM accepting string w or T,w T is a TM accepting string w www.ThesisScientist.comDecidable (or solvable) problems Definition: If f is a reasonable encoding of a decision e problem P over , we say P is decidable (or solvable) if the associated language f (X) X e is a yesinstance of P is recursive. A problem P is undecidable (or unsolvable) if P is not decidable. www.ThesisScientist.comSelfAccepting • SA (Selfaccepting) = w0,1,, , w=e(T) for some TM T and wL(T) • NSA (Nonselfaccepting) = w 0,1,, , w=e(T) for some TM T and wL(T) • E (EncodedTM) = w0,1,, , w=e(T) for some TM T www.ThesisScientist.comNSA is not recursively enumerable We prove by contradiction. Assume NSA is recursively enumerable. Then, there is TM T such that L(T )=NSA. 0 0 Is e(T ) in NSA 0 – If e(T )NSA, then e(T )L(T ) by the definition of NSA 0 0 0 But L(T )=NSA. Thus, contradiction. 0 – If e(T ) NSA, then e(T ) SA and e(T )L(T ) by the 0 0 0 0 definition of SA. But L(T )=NSA. Thus, contradiction. 0 Then, the assumption is false. That is, NSA is not recursively enumerable. www.ThesisScientist.comE is recursive Theorem: E is recursive. Proof: We can construct a regular expression for E according to the definition of the encoding function as follows: + R = S 1 (M ) S = 0 M = Q , A , Q , A , D + Q = 0 + A = 0 D = 0 + 00 + 000 Then, E is regular, and thus recursive. www.ThesisScientist.comSA is recursively enumerable • Construct a TM S accepting SA • If w is not e(T) for some TM T, S rejects w. • If w is e(T) for some TM T, S accepts e(T) iff T accepts e(T). • L(S) = w w=e(T) for some TM T accepting e(T) = SA. • Then, SA is recursively enumerable. E Encode UTM Reject www.ThesisScientist.comSA is not recursive • NSA = E – SA • NSA is not recursively enumerable (from previous theorem), and thus not recursive. • But E is recursive. • From the closure property, if L1 and L2 are recursive, then L1 L2 is recursive. • Using its contrapositive, if L1 L2 is not recursive, then L1 or L2 are not recursive. • Since NSA is not recursive and E is recursive, SA is not recursive. www.ThesisScientist.comCoR.E. Definition • A language L is coR.E. if its complement L is R.E. • It does not mean L is not R.E. Examples: • SA is R.E. SA=ENSA is not R.E. –SA is coR.E., but not R.E. • NSA is not R.E. NSA=ESA is R.E. – NSA is coR.E., but not R.E. • E is recursive, R.E., and coR.E. www.ThesisScientist.comRelationship between R.E., coR.E. and Recursive Languages Theorem: Let L be any language. L is R.E. and co R.E. iff L is recursive. Proof: • () Let L be R.E. and coR.E. Then, L is R.E. Thus, L is recursive. • () Let L be recursive. Then, L is R.E. From the closure under complementation of the class of recursive languages,L is also recursive. Then, L is also R.E. Thus, L is coR.E. www.ThesisScientist.comObservation • A language L is either – recursive – R.E., bot not recursive – coR.E., but not recursive – Neither R.E. nor coR.E. R.E. recursive coR.E. Neither R.E. nor coR.E. www.ThesisScientist.comReduction Definition: Let L and L be languages over  and  , 1 2 1 2 respectively. L is (manyone) reducible to L , 1 2 denoted by LL , if there is a TM M computing a 1 2 function f:   such that wL f(w)L . 1 2 1 2 Definition: Let P and P be problems. P is (manyone) 1 2 1 reducible to P if there is a TM M computing a 2 function f:   such that w is a yesinstance of 1 2 P f(w) is a yesinstance of P . 1 2 www.ThesisScientist.comReduction Definition: A function f:  is a Turingcomputable 1 2 function if there is a Turing machine computing f. Definition: Let L and L be languages over  and  , 1 2 1 2 respectively. L is (manyone) reducible to L , 1 2 denoted by LL , if there is a Turingcomputable 1 2 function f:  such that wL f(w)L . 1 2 1 2 www.ThesisScientist.comMeaning of Reduction P is reducible to P if  TM M computing a 1 2 function f:  such that w is a yes 1 2 instance of P f(w) is a yesinstance of P . 1 2 • If you can map yesinstances of problem A to yesinstances of problem B, then – we can solve A if we can solve B – it doesn’t mean we can solve B if we can solve A – the decidability of B implies the decidability of A www.ThesisScientist.comProperties of reduction Theorem: Let L be a language over . LL. Proof: Let L be a language over . Let f be an identity function from   . Then, there is a TM computing f. Because f is an identity function, wL  f(w)=wL. By the definition, LL. www.ThesisScientist.comProperties of reduction Theorem: Let L and L be languages over . 1 2 If LL , thenLL . 1 2 1 2 Proof: Let L and L be languages over . 1 2 Because LL , there is a function f such that wL 1 2 1 f(w)L , and a TM T computing f. 2 wL f(w)L . 1 2 By the definition,LL . 1 2 www.ThesisScientist.comProperties of reduction Theorem: Let L , L and L be languages over . 1 2 3 If LL and LL , then LL . 1 2 2 3 1 3 Proof: Let L , L and L be languages over . 1 2 3 There is a function f such that wL f(w)L , and a 1 2 TM T1 computing f because LL . 1 2 There is a function g such that wL g(w)L , and a 2 3 TM T2 computing g because LL . 2 3 wLf(w)Lg(f(w))L , and T1T2 computes 1 2 3 g(f(w)). By the definition, LL . 1 3 www.ThesisScientist.comUsing reduction to prove decidability Theorem: If L is recursive, and LL , then L is also 2 1 2 1 recursive. Proof: Let L and L be languages over , LL , and L be 1 2 1 2 2 recursive. Because L is recursive, there is a TM T computing 2 2  . L2 Because LL , there is a TM T computing a function 1 2 1 f such that wL f(w)L . 1 2 www.ThesisScientist.comUsing reduction to prove decidability Construct a TM T=TT . We show that T computes 1 2  . L 1 – If wL , T in T computes f(w)L and T in T computes 1 2 1 2  (f(w)), which is 1. L2 – If wL , T in T computes f(w) L and T in T 1 2 1 2 computes  (f(w)), which is 0. L2 Thus, L is also recursive. 1 www.ThesisScientist.comUsing Reduction to Prove Undecidability Collorary: If L is not recursive, and LL , then L is not 1 1 2 2 recursive. www.ThesisScientist.comUsing reduction to prove R.E. Theorem: If L is R.E., and LL , then L is also R.E. 2 1 2 1 Proof: Let L and L be languages over , LL , and L be 1 2 1 2 2 R.E. Because L is R.E, there is a TM T accepting L . 2 2 2 Because LL , there is a TM T computing a function 1 2 1 f such that wL f(w)L . 1 2 www.ThesisScientist.comUsing reduction to prove R.E. Construct a TM T=TT . We show that T accepts 1 2 L . 1 – If wL , T in T computes f(w)L and T in T accepts 1 2 1 2 f(w). Thus, T accepts w. – If wL , T in T computes f(w)L and T in T does not 1 2 1 2 accept (f(w)). Thus, T does not accept w. Thus, L is also R.E. 1 www.ThesisScientist.comUsing reduction to prove nonR.E. Collorary: If L is not recursively enumerable, and LL , 1 1 2 then L is not recursively enumerable. 2 www.ThesisScientist.comUsing reduction to prove coR.E. Theorem: If L is coR.E., and LL , then L is also 2 1 2 1 coR.E. Proof: Let L and L be languages over , LL , and L be 1 2 1 2 2 coR.E. Because L is coR.E,L is R.E. 2 2 Because LL ,LL . Then,L is R.E. 1 2 1 2 1 Thus, L is coR.E. 1 www.ThesisScientist.comUsing reduction to prove noncoR.E. Collorary: If L is not coR.E., and LL , then L is not 1 1 2 2 coR.E. www.ThesisScientist.comAnother way to prove undecidability Let L1L2. If L1 is not recursive / R.E. recursive coR.E. R.E. / coR.E., then L2 is not recursive / R.E. / Neither R.E. nor coR.E. coR.E. To prove a language L is not recursive: 1. Guess where L is (not R.E. or not coR.E.) 2. Choose another nonrecursive language R which is of the same type 3. Show R  L. www.ThesisScientist.comAnother way to prove undecidability R.E. coR.E. SA NSA recursive Neither R.E. nor coR.E. To prove a language L is not recursive: 1. Guess where L is (not R.E. or not coR.E.) 2. If L is not R.E., then show NSA  L. 3. If L is not coR.E., then show SA  L. www.ThesisScientist.comGuess if it’s rec., R.E., coR.E., or neither Given a TM T, R.E., • does T get to state q on blank tape not coR.E. R.E., not coR.E. • does T accept  • does T output 1 Neither Neither • does T accept everything • is L(T) finite Neither www.ThesisScientist.comProblem of accepting an empty string • We will prove that the problem if a TM accepts an empty string is undecidable. • This problem is corresponding to the following language. – Accept = e(M) M is a TM accepting  • Thus, we will prove that Accept is not recursive. www.ThesisScientist.comAccept is not recursive. Proof: (Guess Accept is in R.E., but not coR.E.) • Show SA  Accept n (We want a Turingcomputable f f(T)=M such that – T accepts e(T)  M accepts  – T does not accept e(T)  M does not accept  • Let f(T)=M is a TM that first writes e(T) after its input and then runs T. • M writes e(T) after its input. If its input is , T has e(T) as input. M WriteT T www.ThesisScientist.comAccept is not co–R.E. Verify that T accepts e(T)  M accepts  M writes e(T) and lets T run. If the input of M is : • when T accepts e(T), M accepts . • when T doesn’t accept e(T), then M doesn’t accept . www.ThesisScientist.comAccept is not co–R.E. Next, we show that there is a TM TF computing f. TF works as follows: • changes the start state of T in e(T) to a new state • add e(WriteT), make its start state the start state of TF, and make the transition from its halt state to T’s start state. Then, SA  Accept. Then,Accept is not coR.E, and is not recursive. www.ThesisScientist.comHalting problem • Problem – Given a Turing machine T and string z, does T halt on z – Given a program P and input z, does P halt on z • Language – Halt = w  w=e(T)e(z) for a Turing machine T halting on z. – Halt = T,z T is a Turing machine halting on z. www.ThesisScientist.comHalting problem is undecidable Proof: Let Halt = T,z T is a Turing machine halting on z. (Guess Halt is in R.E., but not coR.E.) • Show SA  Halt n (We want a Turingcomputable f f(T )=T ,z 1 2 such that – T accepts e(T )  T halts on z 1 1 2 – T does not accept e(T )  T does not halt on z 1 1 2 Then, a possible function is f(T) = T, e(T) because T accepts e(T)  T halts on e(T).) www.ThesisScientist.comHalting problem is undecidable • Let f(X) = Xe(X). f is Turingcomputable because there is a TM that can write an encoding of an input string after the string itself. • If f(T)=Te(T), then T accepts e(T) T halts on e(T). • Then, SA  Halt, and Halt is not coR.E. Thus, Halting problem is undecidable. www.ThesisScientist.comSome other undecidable problems • FINITE Given a TM T, is L(T) finite Guess FINITE is neither R.E. nor coR.E. • To assure L(T) is finite, we need to run T on all possible input and count if T accepts a finite number of strings. • To assure L(T) is infinite, we need to run T on all possible input and count if T accepts an infinite number of strings. www.ThesisScientist.comFINITE is not recursive Let FINITE=T T is a TM such that L(T) is finite. Guess FINITE is neither R.E. nor coR.E. Choose NSA which is not coR.E. to show that NSAFINITE. We want to find a Turingcomputable function f such that TNSA  f(T)=MFINITE TNSA M accepts , and thus L(M) is finite. TNSAM accepts  , and thus L(M) is infinite. Then, let M=f(T) be a TM that runs T on its input, and accepts everything if T halts. AccAll T M www.ThesisScientist.comFINITE is not recursive Now, we will show that TNSA  MFINITE If TNSA, then T does not accept T. Then, M does not get to start AccAll. Thus, M accepts nothing and L(M) is finite. If TNSA, then T accepts T. Then, M gets pass T, and accept everything. Thus, M accepts everything and L(M) is infinite. f is Turingcomputable. Thus, NSA  FINITE. AccAll T Since NSA is not Recursive, neither is M FINITE. www.ThesisScientist.comChecklist  Prove a language is  Prove a problem is recursive, R.E., or coR.E. decidable  Prove closure properties of  Prove a problem is these classes of languages undecidable  Prove properties of reduction  Prove a language is not recursive, not R.E., or not coR.E. www.ThesisScientist.com
Website URL
Comment