Non-RE Languages o suppose the set of all languages is countable o list characteristic vectors of all languages according to the bijection f n f(n 10101010 21010011 31110001 40100011
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 o suppose the set of all languages is countable o list characteristic vectors of all languages according to the bijection f n f(n set x= 1101 10101010 where ith digit≠ ith digit of f( x cannot be in the list 21010011 therefore, the language with 31110001 characteristic vector x is not in the list 40100011
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 la anguages over {0,1} and talk about“ the i-th language.” C onsider 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 language for some particular j Recall: L=[w I w is the Let x be the j-th string i-th binary string and Mis not in the i-th language) 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 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 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