南京大学：《形式语言与自动机 Formal Languages and Automata》课程教学资源（PPT课件讲稿）Decidability, Complexity（P, NP, NPC and related）

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