效绵鼎 Non-RE Languages suppose the set of all languages is countable list characteristic vectors of all languages according to the bijection f: n f(n) 10101010.. 21010011.. 31110001.. 4 0100011
Non-RE Languages suppose the set of all languages is countable list characteristic vectors of all languages according to the bijection f: n f(n) _ 1 0101010… 2 1010011… 3 1110001… 4 0100011… …
效绵鼎 Non-Re Languages suppose the set of all languages is countable list characteristic vectors of all languages according to the bijection f: n f(n) Setx=1101. 10101010. where ith digit ith digit of f(i) x cannot be in the list! 21010011.. therefore,the language with 31110001.. characteristic vector x is not in the list 4 0100011
Non-RE Languages suppose the set of all languages is countable list characteristic vectors of all languages according to the bijection f: n f(n) _ 1 0101010… 2 1010011… 3 1110001… 4 0100011… … set x = 1101… where ith digit ≠ ith digit of f(i) x cannot be in the list! therefore, the language with characteristic vector x is not in the list
赖绵县 Non-RE Languages Lemma:the set of all languages is uncountable Suppose we could enumerate all languages over {0,l}and talk about“thei-th language..” Consider the language L={ww is the i-th binary string and w is not in the i-th language
Non-RE Languages ◼ Lemma: the set of all languages is uncountable ◼ Suppose we could enumerate all languages over {0,1} and talk about “the i-th language.” ◼ Consider the language L = { w | w is the i-th binary string and w is not in the i-th language}
效绵鼎 Proof-Continued Clearly,L is a language over {0,1}. Thus,it is the j-th anguage for som X particular j. Recall:L={ww is the Let x be the j-th string i-th binary string and wis not in the i-th language). Is x in L? If so,x is not in L by definition of L. j-th If not,then x is in L by definition of L. .14
14 Proof – Continued ▪ Clearly, L is a language over {0,1}. ▪ Thus, it is the j-th language for some particular j. ▪ Let x be the j-th string. ▪ Is x in L? ▪ If so, x is not in L by definition of L. ▪ If not, then x is in L by definition of L. Recall: L = { w | w is the i-th binary string and w is not in the i-th language}. x j-th Lj
效绵鼎 Proof-Concluded We have a contradiction:x is neither in L nor not in L,so our sole assumption (that there was an enumeration of the languages)is wrong Comment:This is really bad;there are more languages than TM. E.g.,there are languages that are not recognized by any Turing machine. .15
15 Proof – Concluded ◼ We have a contradiction: x is neither in L nor not in L, so our sole assumption (that there was an enumeration of the languages) is wrong. ◼ Comment: This is really bad; there are more languages than TM. ◼ E.g., there are languages that are not recognized by any Turing machine