# 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