CS代考计算机代写 BU CS 332 – Theory of Computation

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