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)