Computability Decidability 1 Unsolvable problems Computer scientists usually deal with problems which are solvable. We are supposed to find an algorithm to solve a particular problem. Why do we need to know about problems which are unsolvable ? we will not waste time in finding an non-existed algorithm. we will realize that the problem needs to be simplified or altered before we can find an algorithmic solution. unsolvable problems can stimulate our imagination and help us gain an important perspective on computation. 2 Decidable Languages We have seen in the last chapter an undecidable problem, the 10th problem of Hilbert. Now we will show some other problems and consider whether they are decidable by algorithm or not. 3 Decidable Problems Concerning Regular Languages Acceptance problem Whether a finite automata accepts a string ? ADFA = {<B,w>| B is a DFA that accepts input string w} Whether a nondeterministic finite automata accepts a string ? ANFA = {<B,w>| B is a NFA that accepts input string w} Whether a regular expression generates a given string. AREX = {<R,w>| R is a regular expression that generates string w} 4 Decidable Problems concerning Regular Lang. Empty Language problem Whether a language of a finite automata is empty ? EDFA = {<A>| A is a DFA and L(A) = } Equivalence problem Whether two finite automata are equivalent ? EQDFA = {<A,B>| A and B are DFAs and L(A) = L(B)} 5 Theorem 1 ADFA is a decidable language ADFA = {<B,w>| B is a DFA that accepts input string w} Show that the problem of testing whether a given finite automata accepts a given string is decidable Proof idea: Present a TM M that decides ADFA. 6 Proof M = “on input <B,w>, where B is a DFA and w is a string: Simulate B on input w. If the simulation ends in an accept state, accept. If it ends in a nonaccepting state, reject.” Notes: input of M is an encoded string <B,w> B can be represented reasonably as a list of its five components, Q, , , q0 and F. before M starts its computation, M first checks on whether it properly represents a DFA B and a string w. If not, M rejects. 7 Proof: Input Tape w M keeps track of B’s current state and B’s current position in the input w by writing this information down on its tape. B reject accept Machine M 8 Theorem 2 ANFA is a decidable language ANFA = {<B,w>| B is a NFA that accepts input string w} Proof idea: Present a TM N that decides ANFA. N has M as a subroutine. Because M is designed to work with DFAs, N first converts the NFA B it receives as input to a DFA before passing it to M. 9 Proof N = “on input <B,w>, where B is a NFA and w is a string: Convert NFA B to an equivalent DFA C Run TM M from Theorem 1 on input <C,w>. If M accepts, accept; otherwise reject.” 10 Proof: Input Tape w Machine N C reject accept Machine M 11 Theorem 3 AREX is a decidable language AREX = {<R,w>| R is a regular expression that generates string w} Proof idea: Present a TM P that decides AREX. 12 Proof P = “on input <R,w>, where R is a regular expression and w is a string: Convert regular expression R to an equivalent DFA A. Run TM M on input <A,w>. If M accepts, accept; if M rejects , reject.” 13 Theorem 4 EDFA is a decidable language EDFA = {<A>| A is a DFA and L(A) = } Show that the problem of testing whether a given finite automata accepts any strings at all is decidable. Proof idea: A DFA accepts some string if and only if reaching an accept state from the start state by traveling alone the arrows of the DFA is possible. Present a TM T that uses a marking algorithm. 14 Proof T = “on input <A>, where A is a DFA: Mark the start state of A. Repeat until no new states get marked: Mark any state that has a transition coming into it from any state that is already marked. If no accept state is marked, accept; otherwise reject.” A is empty 15 Theorem 5 EQDFA is a decidable language EQDFA = {<A,B>| A and B are DFAs and L(A) = L(B)} Show that the problem of testing whether 2 DFAs recognize the same language is decidable. Proof idea: Construct a new DFA C from A and B, where C accepts only those strings that are accepted by either A or B but not by both. If A and B recognize the same language, C will accept nothing. Test whether L(C) is empty by the theorem 4.4 16 L(C) Symmetric difference of L(A) and L(B) L(C) = (L(A) L(B)) (L(A) L(B)) L(A) L(B) C is also a DFA as the class of regular language is closed under complementation, union and intersection 17 Proof F = “on input <A,B>, where A and B are DFAs: Construct DFA C as described. Run TM T from Theorem 4 on input <C> If T accepts, accept. If T rejects, reject.” 18 Proof Machine F Machine T C reject reject accept accept 19 Decidable Problems concerning to Context-Free Language Acceptance problem Whether a CFG accepts a string ? ACFG = {<G,w>| G is a CFG that accepts input string w} Emptiness problem Whether a CFG generates any strings at all ? ECFG = {<G>| G is a CFG and L(G) = } Equivalent problem Whether two CFGs generate the same language ? EQCFG = {<G,H>| G and H are CFGs and L(G) = L(H)} 20 Theorem 6 ACFG is a decidable language ACFG = {<G,w>| G is a CFG that generates string w} Proof idea: Naïve idea : Go through every derivations to determine whether any is a derivation of w. But this algorithm will not halt if w is not a member of G. Better approach: We need to ensure that the algorithm tries only finitely many derivations, so use CNF form. any derivation of w has 2n-1 steps, where n is the length of w. 21 Proof S = “on input <G,w>, where G is a CFG and w is a string: Convert G to an equivalent grammar in Chomsky Normal Form. List all derivations with 2n-1 steps, where n is the length of w. If any of these derivations generate w, accept; if not, reject.” 22 CFLs and PDAs As we can convert back and forth between CFLs and PDAs. Hence, everything we say about the decidability of problems concerning CFLs applies well to PDAs. 23 Theorem 7 ECFG is a decidable language ECFG = {<G>| G is a CFG and L(G) = } Proof idea: Naïve idea : to determine whether L(G) = try going through all possible w’s, one by one. But there are infinitely many w’s to try, so this algorithm could end up running forever. Better approach: We need to test whether the start variable can generate a string of terminals. Determine for each variable whether that variable is capable of generating a string of terminals, the algorithm keeps track of this information by placing a mark on that variable. 24 Proof R = “on input <G>, where G is a CFG : Mark all terminal symbols in G. Repeat until no new variables get marked Mark any variable A where G has a rule AU1 U2… Uk and each symbol U1 , …, Uk has already been marked. If the start symbol is not marked, accept; otherwise reject. ” G is empty 25 EQCFG Consider the problem of testing whether 2 CFGs generate the same language. ECFG = {<G,w>| G is a CFG that generates string w} Proof idea: Naïve idea : use the same method as theorem 4.5 But CFL is not closed under complementation or intersections. In fact, ECFG is not decidable. We’ll prove it in the next chapter. 26 Theorem 8 “Every context-free language is decidable.” We show that every CFL is decidable. Proof idea: Naïve (bad) idea : try to convert a PDA for A directly to a TM. the PDA for A may be nondeterministic, so we get an NTM which we can convert into a deterministic TM. however, PDA can have some branches go on forever, reading and writing the stack without coming to a halt. therefore our TM will not be a decider. Better approach: We prove this theorem with the TM S in Theorem 6 to decide ACFG. 27 Proof Let G be a CFG for A and design a TM MG that decides A. We build a copy of G into MG. It works as follow. MG = “on input w: Run TM S on input <G,w> If this machine accepts, accept; if it rejects, reject.” 28 Proof Machine MG Machine S 1. Convert G to CNF form. 2. List all derivations with 2n-1 steps, where n is the length of w. 3. If any of these derivations generate w, accept; if not, reject. accept reject accept reject 29 Relationship among classes of Language Turing-recognizable Regular Context-free Decidable 30 Non Recursively Enumerator language We want to find a language that is not Recursively Enumerable This language is not accepted by any Turing Machine It can’t be implemented on (contemporary) computer. Example: Verify that the program we wrote performs as specified (that it is correct). Halting problem : Testing whether a TM accepts a given input string (ATM) 31 Theorem 9 ATM = {<M,w>| M is a TM and M accepts w}. ATM is undecidable. Proof: observe that ATM is Turing-recognizable. We try to find a TM (U) that recognizes ATM. 32 Halting Problem U = “On input <M,w>, where M is a TM and w is a string: Simulate M on input w. If M ever enters its accept state, accept; if M ever enters its reject state, reject.” Note: U loops on input <M,w> if M loops on w, that’s why U doesn’t decide ATM. 33 Universal Turing Machine proposed by Turing. a machine is called universal if it is capable to simulate any other Turing machine from the description of that machine. played an important early role in stimulating the development of stored-program computers. 34 The Diagonalization method discovered by Georg Cantor in 1873. is the proof of the undecidability of the halting problem. using countable and uncountable set to prove. Idea is : we want to prove that set of Turing-recognizable language is uncountable while set of Turing machine is countable. 35 Cantor’s problem Concerned with the problem of measuring the sizes of infinite sets. If we have 2 infinite sets, how can we tell whether one is larger than the other or whether they are of the same size ? Naïve: try to count the elements of the infinite set, we will never finish! 36 Cantor’s problem Better approach: Observe that 2 finite sets are of the same size if the elements of the one set can be paired with the element of the other set. We can extend this idea to infinite sets. 37 Definition: Correspondence Consider 2 sets, A and B, and a function f from A to B. Say that f is one-to-one if it never maps 2 different elements to the same place that is, f(a) f(b) whenever a b. Say that A and B are the same size if there is a one-to-one, onto function f: AB. one-to-one and onto is called Correspondence 38 Example Let N be the set of Natural numbers {1,2,3,…} be the set of even natural numbers {2,4,6,…} Using cantor’s method, we can see that N and have the same size. n f(n) 1 2 2 4 3 ... 6 ... 39 Definition : Countable A set A is countable if either it is finite or it has the same size as N. 40 Example Let N be the set of Natural numbers {1,2,3,…} Q be the set of positive rational numbers Q = {m/n |m,n N } Q seems the be bigger than N but actually they have the same size. Using cantor’s method, we list all the elements of Q and then pair each element with the element of N. We have to ensure that every member of Q appears only once on the list. 41 Correspondence of N and Q 1 1 1 2 1 3 1 4 1 5 2 1 2 2 2 3 2 4 2 5 3 1 3 2 3 3 3 4 3 5 4 1 4 2 4 3 4 4 4 5 5 1 5 2 ... . . . 42 Trick We pair the first element of Q on the list with the number 1 from N. the second element of Q on the list with the number 2 from N. … After seeing the corresponding of N and Q, we can see that as each curve Q has finite number of elements which can be mapped with elements of N, thus both sets have same size. 43 Theorem 4.14 R is uncountable R is the set of real number. Proof by the diagonalization method. 44 Proof by contradiction : suppose that a correspondence f existed between N and R. means that we must pair all the members of N with all the members of R. show that f fails to work as it should. How to show ? finding an x in R that is not paired with anything in N. 45 Proof Finding x by constructing it. choose each digit of x to make x different from one of the real numbers that is paired with an element of N Sure that x is different from any real number that is paired. 46 Illustration of the idea suppose we have a corresponding f: we construct x by let the first digit of x be anything different from the first fractional digit of f(1). let the second digit of x be anything different from the second fractional digit of f(2). … thus we can construct x which is different from f(n) for any n. n f(n) 1 0.123456 2 0.500000 3 ... 0.759685 ... n f(n) 1 0.423456 2 0.530000 3 ... 0.756685 ... 47 Corollary 4.15 Some languages are not Turing-recognizable. Proof idea: set of Turing-recognizable language is uncountable while set of Turing machine is countable. Because each Turing machine can recognize a single language and there are more languages than TMs, some languages are not recognized by any TM. Thus, there exists some languages which are not Turingrecognizable. 48 set of all TMs is countable. Proof idea: first of all we have to observe that the set of all * is countable, for any alphabet . with only finitely many strings of each length, we may form a list of * by written down all strings of length 0, length 1, length 2 and so on. 49 set of all TMs is countable. Secondly We can encode each TM into a string <M> as the set of all strings is countable therefore the set of all TMs is countable. 50 set of all languages is uncountable Proof idea: first of all we have to observe that the set of all infinite binary sequence is uncountable An infinite binary sequence is an unending sequence of 0s and 1s. we can prove by the diagonalization method. (imagine as the same way as R) 51 set of all languages is uncountable Secondly Let B be the set of all infinite binary sequences. Let L be the set of all languages over alphabet . Show that L is uncountable by giving correspondence with B. the idea is that “as B is uncountable thus L is also uncountable.” 52 set of all languages is uncountable Correspondence of L and B Show that both sets have the same size. Let * = {s1,s2,…}. Each language A L has a unique sequence of B. (oneto-one and onto) Characteristic sequence of A, (A) The ith bit of that sequence is a 1 if si A and is a 0 if si A. 53 set of all languages is uncountable Example : Characteristic sequence * = { , 0 , 1 , 00 , 01 , 10 , A = { (A) = { 0 0 , 1 1 1 000 , 001 , … } ; 00 , 01 0 1 1 , 000 , 001 , … } ; 0 0 1 1 … } ; The function f: L B, where f(A) equals the Characteristic sequence of A, is one-to-one and onto and hence a correspondence. Therefore, as B is uncountable, L is uncountable as well. 54 The Halting Problem We have proved that there are some languages which are not Turing-recognizable. Now, we want to show that such a TM which can recognize the non Turing-recognizable language doesn’t exist. 55 Proof of Theorem 9 ATM is undecidable. Proof: Consider = {a}. The set of all strings is * = {,a, aa, aaa, aaaa…} = {,a1, a2, a3, a4…} the set of all TMs is countable, thus we can order them as M1, M2, M3,… to indicate which language is accepted by what machine, we can again use the characteristic sequence of that language. 56 Proof of Theorem 9 Example: assume a machine Mi accepts a language L(Mi) L(Mi) = {a2, a4, a6} we can write * L(Mi) = { a1 , a2 , a3 , a4 = { 0 1 1 0 , a5 , a6 , a7 , 0 1 0 a8 0 , , … } ; , … } ; 57 Proof of Theorem 9 For each machine, we can write its characteristic sequence a 1 a 2 a 3 a 4 L(M ) 1 0 1 0 1 L(M ) 1 0 0 1 ) 0 1 1 1 ) 0 0 0 1 L(M L(M 2 3 4 58 Proof of Theorem 9 Consider the language i i L { a : a L ( M i )} L consists from the 1’s in the diagonal 59 a L(M L(M 2 3 4 a 2 a 3 a 4 0 1 0 1 ) 1 0 0 1 ) 0 1 1 1 ) 0 0 0 1 4 L(M ) 1 L(M 1 3 L { a , a , } 60 Proof of Theorem 9 Since L is a properly defined language, we can consider its complement Consider the language L i i i i L { a : a L ( M i )} L { a : a L ( M i )} L consists from the 0’s in the diagonal 61 a L(M L(M 2 3 4 a 2 a 3 a 4 0 1 0 1 ) 1 0 0 1 ) 0 1 1 1 ) 0 0 0 1 L(M ) 1 L(M 1 1 2 L { a , a , } 62 Proof of Theorem 4.9 Claim 1: Language L is not recursively enumerable If we can prove that it is not recursively enumerable, we can now find a language which is not Turing recognizable. 63 Proof: Claim 1 Assume for contradiction that is recursively enumerable There must exist some machine that accepts L L Mk L(M k ) L 64 a L(M ) 1 L(M L(M L(M 2 3 4 1 a 2 a 3 a 4 0 1 0 1 ) 1 0 0 1 ) 0 1 1 1 ) 0 0 0 1 Question: M k M1? 65 a L(M ) 1 L(M L(M L(M 2 3 4 Answer: 1 a 2 a 3 a 4 0 1 0 1 ) 1 0 0 1 ) 0 1 1 1 ) 0 0 0 1 M k M1 a L(M k ) 1 1 a L(M 1) 66 a L(M ) 1 L(M L(M L(M 2 3 4 1 a 2 a 3 a 4 0 1 0 1 ) 1 0 0 1 ) 0 1 1 1 ) 0 0 0 1 Question: M k M 2 ? Answer: M k M 2 a L(M k ) 2 2 a L(M 2 ) 67 a L(M ) 1 L(M L(M L(M 2 3 4 1 a 2 a 3 a 4 0 1 0 1 ) 1 0 0 1 ) 0 1 1 1 ) 0 0 0 1 Question: M k M 3 ? Answer: M k M 3 a L(M k ) 3 3 a L(M 3 ) 68 Proof: Claim 1 Similarly: Mk Mi for any i Because either: i a L(M k ) i a L(M i ) i or a L(M k ) i a L(M i ) 69 Proof: Claim 1 Therefore, the machine M k cannot exist Therefore, the language L is not recursively enumerable End of Proof 70 Observation: There is no algorithm that describes L (otherwise L would be accepted by some Turing Machine) 71 Non Recursively Enumerable L Recursively Enumerable Recursive 72 Testing whether TM accepts a given string : ATM Try to construct a TM (H) to decide whether another TM (M) accepts a string (w) or not. H is decider on (M,w) accept if M accepts w H(M,w) = reject if M rejects w 73 Testing whether TM accepts a given string : ATM If w = the encoded string <M> H is decider on (M,<M>) H(M,<M>) accept if M accepts <M> reject if M rejects <M> = 74 Testing whether TM accepts a given string : ATM Now we construct a new TM (D) with H as a subroutine. D does opposite to what its subroutine does. D = “On input <M>, where M is a TM, Run H on input <M,<M>) Output the opposite to what H outputs; that is, if H accepts, reject and if H rejects, accept.” 75 Testing whether TM accepts a given string : ATM accept if H rejects <M> reject if H accepts <M> accept if M rejects <M> reject if M accepts <M> D(<M>) = D(<M>) = 76 Testing whether TM accepts a given string : ATM D(<M>) H (M,<M>) M (<M>) if M accepts <M> then H accepts if M rejects <M> then H rejects accept reject reject accept 77 Testing whether TM accepts a given string : ATM running M on <M> M1 M M1 2 M 3 M 1 4 1 M2 1 M3 1 1 M4 1 1 1 1 78 Testing whether TM accepts a given string : ATM output of H M1 M 2 M 3 M 4 M1 1 0 0 1 M2 0 0 1 0 M3 1 1 0 0 M4 1 1 1 1 79 Testing whether TM accepts a given string : ATM Output of D M1 M 2 M 3 M 4 D M1 1 0 0 1 1 M2 0 0 1 0 1 M3 1 1 0 0 0 M4 1 1 1 1 1 0 D 0 1 1 ? 80 A Language which is Recursively Enumerable and not Recursive 81 We want to find a language which Is recursively enumerable There is a Turing Machine that accepts the language But not recursive The machine doesn’t halt on some input 82 Proof We will prove that the language i i L { a : a L ( M i )} Is recursively enumerable but not recursive 83 a L(M L(M 2 3 4 a 2 a 3 a 4 0 1 0 1 ) 1 0 0 1 ) 0 1 1 1 ) 0 0 0 1 L(M ) 1 L(M 1 3 4 L { a , a , } 84 Theorem: The language i i L { a : a L ( M i )} is recursively enumerable Proof: We will give a Turing Machine that accepts L 85 Turing Machine that accepts L For any input string w • Compute i for which w a i • Find Turing machine M i (using the enumeration procedure for Turing Machines) i • Simulate M i on input a • If M i accepts, then accept w End of Proof 86 Observation: Recursively enumerable i i L { a : a L ( M i )} Not recursively enumerable i i L { a : a L ( M i )} (Thus, also not recursive) 87 Theorem: The language i i L { a : a L ( M i )} is not recursive Proof: Assume for contradiction that L is recursive 88 Proof Then L is recursive But we know: L is not recursively enumerable thus, not recursive CONTRADICTION! Therefore, L is not recursive End of Proof 89 Non Recursively Enumerable L Recursively Enumerable L Recursive 90 Theorem A language is decidable (recursive) if and only if it is both Turing-recognizable and CoTuring-recognizable. Co-Turing-recognizable language is the the complement of a Turing-recognizable language. 91 Corollary ATM is not Turing-recognizable. Proof: ATM is Turing-recognizable. if ATM is Turing-recognizable, ATM would be decidable. But ATM is not decidable, thus ATM must not be Turing-recognizable. 92 Recursively Enumerable and Recursive Languages 93 Definition: A language is recursively enumerable (rekursivt uppräknelig) if some Turing machine accepts it 94 Let L be a recursively enumerable language and M the Turing Machine that accepts it For string w : if w L then M halts in a final state if w L then M halts in a non-final state or loops forever 95 Definition: A language is recursive if some Turing machine accepts it and halts on any input string In other words: A language is recursive if there is a membership algorithm for it 96 Let L be a recursive language and M the Turing Machine that accepts it For string w : if w L then M halts in a final state if w L then M halts in a non-final state 97 We will prove: 1. There is a specific language which is not recursively enumerable (not accepted by any Turing Machine) 2. There is a specific language which is recursively enumerable but not recursive 98 Non Recursively Enumerable Recursively Enumerable Recursive 99 We will first prove: • If a language is recursive then there is an enumeration procedure for it • A language is recursively enumerable if and only if there is an enumeration procedure for it 100 Theorem: if a language L is recursive then there is an enumeration procedure for it 101 Proof: Enumeration Machine ~ M Enumerates all strings of input alphabet M Accepts L 102 If the alphabet is { a , b } then ~ M can enumerate strings as follows: a b aa ab ba bb aaa aab ...... 103 Enumeration procedure Repeat: ~ M generates a string w M checks if w L YES: print w to output NO: ignore w End of Proof 104 Example: ~ M a b aa ab ba bb aaa aab ...... L {b , ab , bb , aaa ,....} L(M ) Enumeration Output b b ab ab bb aaa bb aaa ...... ...... 105 Theorem: if language L is recursively enumerable then there is an enumeration procedure for it 106 Proof: Enumeration Machine ~ M Enumerates all strings of input alphabet M Accepts L 107 If the alphabet is { a , b } then ~ M can enumerate strings as follows: a b aa ab ba bb aaa aab 108 NAIVE APPROACH Enumeration procedure Repeat: ~ M generates a string w M checks if w L YES: print w to output NO: ignore w Problem: If w L machine M may loop forever 109 BETTER APPROACH ~ M Generates first string w1 M ~ M executes first step on w1 Generates second string w 2 M executes first step on w 2 second step on w1 110 ~ M Generates third string w 3 M executes first step on w 3 second step on w 2 third step on w1 And so on............ 111 Step in string w1 w2 w3 w4 1 1 1 1 2 2 2 2 3 3 3 3 112 If for any string w i machine M halts in a final state then it prints w i on the output End of Proof 113 Theorem: If for language L there is an enumeration procedure then L is recursively enumerable 114 Proof: Input Tape w Machine that accepts L Enumerator for L Compare 115 Turing machine that accepts L For input string w Repeat: • Using the enumerator, generate the next string of L • Compare generated string with w If same, accept and exit loop End of Proof 116 We have proven: A language is recursively enumerable if and only if there is an enumeration procedure for it 117 A Language which is not Recursively Enumerable 118 We want to find a language that is not Recursively Enumerable This language is not accepted by any Turing Machine 119 {a } Consider alphabet Strings: a , aa , aaa , aaaa , a 1 a 2 a 3 a 4 120 Consider Turing Machines that accept languages over alphabet {a } They are countable: M 1, M 2 , M 3 , M 4 , 121 Example language accepted by Mi L ( M i ) { aa , aaaa , aaaaaa } 2 4 6 L ( M i ) {a , a , a } Alternative representation a L(M i ) 1 0 a 1 2 a 3 0 a 4 1 a 5 0 a 1 6 a 7 0 122 a 1 a 2 a 3 a 4 L(M 1) 0 1 0 1 L(M 2 ) 1 0 0 1 L(M 3 ) 0 1 1 1 L(M 4 ) 0 0 0 1 123 Consider the language i i L { a : a L ( M i )} L consists from the 1’s in the diagonal 124 a 1 a 2 a 3 a 4 L(M 1) 0 1 0 1 L(M 2 ) 1 0 0 1 L(M 3 ) 0 1 1 1 L(M 4 ) 0 0 0 1 3 4 L { a , a , } 125 Consider the language L i i i i L { a : a L ( M i )} L { a : a L ( M i )} L consists from the 0’s in the diagonal 126 a 1 a 2 a 3 a 4 L(M 1) 0 1 0 1 L(M 2 ) 1 0 0 1 L(M 3 ) 0 1 1 1 L(M 4 ) 0 0 0 1 1 2 L { a , a , } 127 Theorem: Language L is not recursively enumerable 128 Proof: Assume for contradiction that L is recursively enumerable There must exist some machine M k that accepts L L(M k ) L 129 a 1 a 2 a 3 a 4 L(M 1) 0 1 0 1 L(M 2 ) 1 0 0 1 L(M 3 ) 0 1 1 1 L(M 4 ) 0 0 0 1 Question: M k M1? 130 a 1 a 2 a 3 a 4 L(M 1) 0 1 0 1 L(M 2 ) 1 0 0 1 L(M 3 ) 0 1 1 1 L(M 4 ) 0 0 0 1 1 Answer: M k M1 a L(M k ) 1 a L(M 1) 131 a 1 a 2 a 3 a 4 L(M 1) 0 1 0 1 L(M 2 ) 1 0 0 1 L(M 3 ) 0 1 1 1 L(M 4 ) 0 0 0 1 Question: Mk M2? 132 a 1 a 2 a 3 a 4 L(M 1) 0 1 0 1 L(M 2 ) 1 0 0 1 L(M 3 ) 0 1 1 1 L(M 4 ) 0 0 0 1 2 Answer: Mk M2 a L(M k ) 2 a L(M 2 ) 133 a 1 a 2 a 3 a 4 L(M 1) 0 1 0 1 L(M 2 ) 1 0 0 1 L(M 3 ) 0 1 1 1 L(M 4 ) 0 0 0 1 Question: M k M 3 ? 134 a 1 a 2 a 3 a 4 L(M 1) 0 1 0 1 L(M 2 ) 1 0 0 1 L(M 3 ) 0 1 1 1 L(M 4 ) 0 0 0 1 3 Answer: Mk M3 a L(M k ) 3 a L(M 3 ) 135 Similarly: Mk Mi for any i Because either: i a L(M k ) i a L(M i ) i or a L(M k ) i a L(M i ) 136 Thus the machine M k cannot exist Therefore, the language L is not recursively enumerable End of Proof 137 Observation: There is no algorithm that describes L (otherwise L would be accepted by some Turing Machine) 138 Non Recursively Enumerable L Recursively Enumerable Recursive 139 A Language which is Recursively Enumerable and not Recursive 140 We want to find a language which Is recursively enumerable There is a Turing Machine that accepts the language But not recursive The machine doesn’t halt on some input 141 We will prove that the language i i L { a : a L ( M i )} Is recursively enumerable but not recursive 142 a 1 a 2 a 3 a 4 L(M 1) 0 1 0 1 L(M 2 ) 1 0 0 1 L(M 3 ) 0 1 1 1 L(M 4 ) 0 0 0 1 3 4 L { a , a , } 143 Theorem: The language i i L { a : a L ( M i )} is recursively enumerable 144 Proof: We will give a Turing Machine that accepts L 145 Turing Machine that accepts L For any input string w • Compute i , for which w a i • Find Turing machine M i (using the enumeration procedure for Turing Machines) • Simulate M i on input a i • If M i accepts, then accept w End of Proof 146 Observation: Recursively enumerable i i L { a : a L ( M i )} Not recursively enumerable i i L { a : a L ( M i )} (Thus, also not recursive) 147 Theorem: The language i i L { a : a L ( M i )} is not recursive 148 Proof: Assume for contradiction that L is recursive Take the Turing Machine M that accepts L M halts on any input: If M accepts then reject If M rejects then accept Then L is recursive 149 L is recursive But we know: L is not recursively enumerable thus, not recursive CONTRADICTION! Therefore, L is not recursive End of Proof 150 Non Recursively Enumerable L Recursively Enumerable L Recursive 151

Descargar
# Languages and Finite Automata