BU CS 332 – Theory of Computation
Lecture 14:
• More on decidability
Reading: Sipser Ch 4.2
• Countable and uncountable sets
Mark Bun March 18, 2020
Last Time
3/18/2020
CS332 ‐ Theory of Computation 2
𝐃𝐅𝐀 𝐂𝐅𝐆
decidable decidable
𝐃𝐅𝐀 𝐂𝐅𝐆
decidable decidable
decidable
𝐃𝐅𝐀
One more decidable language (Sipser 4.10)
Theorem:
is decidable
Lemma: Let be a DFA with states. Then accepts infinitely many strings if and only if accepts some string of length .
3/18/2020
CS332 ‐ Theory of Computation 3
One more decidable language (Sipser 4.10)
Theorem:
Proof: The following TM decides :
is decidable
On input
, where is a DFA with states:
be a DFA recognizing all strings of length
1. 2. 3.
Let Let
be a DFA recognizing
Run the decider for on input Accept if it
rejects, and reject if it accepts. 3/18/2020 CS332 ‐ Theory of Computation
4
Problems in Language Theory
3/18/2020
5
𝐃𝐅𝐀 𝐂𝐅𝐆
𝐓𝐌
decidable decidable
?
𝐃𝐅𝐀 𝐂𝐅𝐆
𝐓𝐌
decidable decidable
?
𝐃𝐅𝐀 𝐂𝐅𝐆
𝐓𝐌
decidable ? CS332 ‐ Theory of Computation
?
Undecidability
These natural computational questions about computational models are undecidable
I.e., computers cannot solve these problems no matter how much time they are given
3/18/2020 CS332 ‐ Theory of Computation 6
Countability and Diagonalizaiton
3/18/2020 CS332 ‐ Theory of Computation 7
Set Theory Review
A function is • 1‐to‐1 (injective) if
for all
• onto (surjective) if for all there exists such that
• a correspondence (bijective) if it is 1‐to‐1 and onto, i.e., every has a unique with
3/18/2020
CS332 ‐ Theory of Computation 8
How can we compare sizes of infinite sets?
Definition: Two sets have the same size if there is a bijection between them
A set is countable if
• it is a finite set, or
• it has the same size as , the set of natural numbers
3/18/2020 CS332 ‐ Theory of Computation 9
Examples of countable sets
•
• •
• • •
3/18/2020
CS332 ‐ Theory of Computation 10
How to show that is countable? 1,1 2,1 3,1 4,1 5,1 …
1,2 2,2 3,2 4,2 5,2 1,3 2,3 3,3 4,3 5,3 1,4 2,4 3,4 4,4 5,4 1,5 2,5 3,5 4,5 5,5
… … …
3/18/2020 CS332 ‐ Theory of Computation
11
More examples of countable sets
•
∗
• •
So what isn’t countable?
3/18/2020 CS332 ‐ Theory of Computation 12
Cantor’s Diagonalization Method
Georg Cantor 1845‐1918
“Set theory is wrong…utter nonsense…laughable” –L. Wittgenstein
3/18/2020
CS332 ‐ Theory of Computation 13
• Invented set theory
• Defined countability, uncountability,
cardinal and ordinal numbers, …
Some praise for his work:
“Scientific charlatan…renegade…corruptor of youth” –L. Kronecker
Sylvester Medal, Royal Society, 1904
Uncountability of the reals
Theorem: The real interval is uncountable. Proof: Assume for the sake of contradiction it were
countable, and let
be a correspondence
Construct
3/18/2020
… where digit of
CS332 ‐ Theory of Computation 14
𝑛
𝑓𝑛
0 . 𝑑 𝑑 𝑑 𝑑 𝑑 … 0 . 𝑑 𝑑 𝑑 𝑑 𝑑 … 0 . 𝑑 𝑑 𝑑 𝑑 𝑑 … 0 . 𝑑 𝑑 𝑑 𝑑 𝑑 … 0 . 𝑑 𝑑 𝑑 𝑑 𝑑 …
1 2 3 4 5
which does not appear in this table – contradiction!
Uncountability of the reals
A concrete example:
Construct
3/18/2020
… where digit of CS332 ‐ Theory of Computation
15
1 2 3 4 5
which does not appear in this table – contradiction!
Diagonalization
This process of constructing a counterexample by “contradicting the diagonal” is called diagonalization
3/18/2020 CS332 ‐ Theory of Computation 16
What if we try to do this with the rationals?
What happens if we try to use this argument to show that
Let
[rational numbers in ] is uncountable? be a correspondence
Construct
which does not appear in this table
3/18/2020
… where digit of CS332 ‐ Theory of Computation
17
1 2 3 4 5
A general theorem about set sizes
Theorem: Let be a set. Then the power set does not have the same size as .
Proof: Assume for the sake of contradiction that there is a correspondence
Goal: Construct a set that cannot be the output for any
3/18/2020 CS332 ‐ Theory of Computation 18
…
Diagonalization argument
Assume a correspondence
𝑥
𝑥 𝑥 𝑥 𝑥
3/18/2020
CS332 ‐ Theory of Computation 19
…
Diagonalization argument
Assume a correspondence
𝑥
𝑥 ∈𝑓𝑥? 𝑥 ∈𝑓𝑥? 𝑥 ∈𝑓𝑥? 𝑥 ∈𝑓𝑥? …
𝑥 𝑥 𝑥 𝑥
YNYY NNYY
Define Put
YYYN NNYN
by flipping the diagonal:
3/18/2020 CS332 ‐ Theory of Computation 20
…
Example
Let
Ex.
Construct
3/18/2020
CS332 ‐ Theory of Computation
21
𝑥 1 2 3
1∈𝑓𝑥? 2 ∈𝑓𝑥? 3 ∈𝑓𝑥?
…
A general theorem about set sizes
Theorem: Let be a set. Then the power set does not have the same size as .
Proof: Assume for the sake of contradiction that there is a correspondence
Construct a set that cannot be the output
for any If
:
for some ,
3/18/2020
CS332 ‐ Theory of Computation 22
then
if and only if