NANJING UNIVERSITY Decidability The diagonalization method The halting problem is undecidable
The diagonalization method The halting problem is undecidable Decidability
效绵鼎 Undecidability decidable all languages regular languages context free languages RE decidable c re c all languages our goal:prove these containments proper
Undecidability decidable RE all languages our goal: prove these containments proper regular languages context free languages all languages decidable RE
效绵鼎 Countable and Uncountable Sets the natural numbers N={1,2,3,...}are countable Definition:a set S is countable if it is finite,or it is infinite and there is a bijection f:N→S
Countable and Uncountable Sets ◼ the natural numbers N = {1,2,3,…} are countable ◼ Definition: a set S is countable if it is finite, or it is infinite and there is a bijection f: N → S
效绵鼎 Example Countable Set The positive rational numbers Q=(m/n |m,n EN} are countable. Proof: 1/1/21/31/41/51/6. 2U12/22/32142152/6. 3/13/23/33143/53/6 4/14/24/34/44/54/6.. 5/1
Example Countable Set ◼ The positive rational numbers Q = {m/n | m, n N } are countable. ◼ Proof: 1/1 1/2 1/3 1/4 1/5 1/6 … 2/1 2/2 2/3 2/4 2/5 2/6 … 3/1 3/2 3/3 3/4 3/5 3/6 … 4/1 4/2 4/3 4/4 4/5 4/6 … 5/1 … …
效绵鼎 Example Uncountable Set Theorem:the real numbers R are NOT countable (they are“uncountable"). How do you prove such a statement? assume countable (so there exists bijection f) derive contradiction (some element not mapped to by f) o technique is called diagonalization (Cantor)
Example Uncountable Set Theorem: the real numbers R are NOT countable (they are “uncountable”). ◼ How do you prove such a statement? assume countable (so there exists bijection f) derive contradiction (some element not mapped to by f) technique is called diagonalization (Cantor)
效绵 Example Uncountable Set ■Proof: suppose R is countable list R according to the bijection f: n f(n) 13.14159. 25.55555.. 30.12345. 40.50000
Example Uncountable Set ◼ Proof: suppose R is countable list R according to the bijection f: n f(n) _ 1 3.14159… 2 5.55555… 3 0.12345… 4 0.50000… …
效绵 Example Uncountable Set ■Proof: suppose R is countable list R according to the bijection f: f(n) set x 0.a azaga4... 13.14159. where digit a#ith digit after decimal 25.55555.. point of f(i)(not 0,9) e.g.×=0.2312. 30.12345.. x cannot be in the list! 40.50000
Example Uncountable Set ◼ Proof: suppose R is countable list R according to the bijection f: n f(n) _ 1 3.14159… 2 5.55555… 3 0.12345… 4 0.50000… … set x = 0.a1a2a3a4… where digit ai ≠ i th digit after decimal point of f(i) (not 0, 9) e.g. x = 0.2312… x cannot be in the list!
效绵鼎 Non-RE Languages Theorem:there exist languages that are not Recursively Enumerable. Proof outline: the set of all TMs is countable the set of all languages is uncountable the function L:{TMslanguages} cannot be onto
Non-RE Languages Theorem: there exist languages that are not Recursively Enumerable. Proof outline: the set of all TMs is countable the set of all languages is uncountable the function L: {TMs} →{languages} cannot be onto
效绵 Non-RE Languages Lemma:the set of all TMs is countable. Proof: the set of all strings >is countable,for a finite alphabet >With only finitely many strings of each length,we may form a list of >by writing down all strings of length 0,all strings of length 1,all strings of length 2,etc. each TM M can be described by a finite-length string s Generate a list of strings and remove any strings that do not represent a TM to get a list of TMs
Non-RE Languages ◼ Lemma: the set of all TMs is countable. ◼ Proof: the set of all strings * is countable, for a finite alphabet . With only finitely many strings of each length, we may form a list of * by writing down all strings of length 0, all strings of length 1, all strings of length 2, etc. each TM M can be described by a finite-length string s Generate a list of strings and remove any strings that do not represent a TM to get a list of TMs
效缥鼎 Non-Re languages Lemma:the set of all languages is uncountable Proof: fix an enumeration of all strings s,s2,S3,... (for example,lexicographic order) 0 a language L is described by its characteristic vector XL whose ith element is 0 ifs;is not in L and 1 ifs:is in L
Non-RE Languages ◼ Lemma: the set of all languages is uncountable ◼ Proof: fix an enumeration of all strings s1 , s2 , s3 , … (for example, lexicographic order) a language L is described by its characteristic vector L whose ith element is 0 if si is not in L and 1 if si is in L