大房 NANJING UNIVERSITY Decidability The diagonalization method The halting problem is undecidable
The diagonalization method The halting problem is undecidable Decidability
Undecidability decidable all languages reqular languages context free languages RE decidable cre 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
A 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, nEN) are countable Proof 11/21/3141/516 212/22/3242/526 3/13/23/33/43/536 4/14/24/3444/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 … …
A Example Uncountable Set Theorem: the real numbers r are not countable(they are uncountable) How do you prove such a statement? o assume countable(so there exists bijection f) o 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)