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

BU CS 332 – Theory of Computation

Lecture 14:

• Countability

• Undecidable Languages

Reading: Sipser Ch 4.2

Mark Bun March 18, 2020

Last Time

𝑨𝑨𝐃𝐃𝐃𝐃𝐃𝐃 𝑨𝑨𝐂𝐂𝐃𝐃𝐂𝐂

𝑬𝑬𝑬𝑬 𝐃𝐃𝐃𝐃𝐃𝐃 𝐂𝐂𝐃𝐃𝐂𝐂

decidable decidable

𝑬𝑬𝑬𝑬

decidable decidable

𝐃𝐃𝐃𝐃𝐃𝐃

decidable

3/17/2020

CS332 – Theory of Computation

2

One more decidable language (Sipser 4.10)

Theorem: 𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼DFA =

𝐷𝐷 𝐷𝐷 is a DFA that accepts infinitely many strings}

Lemma: Let 𝐷𝐷 be a DFA with 𝑛𝑛 states. Then 𝐷𝐷 accepts infinitely many strings if and only if 𝐷𝐷 accepts some string of length ≥ 𝑛𝑛.

is decidable

3/18/2020 CS332 – Theory of Computation 3

One more decidable language (Sipser 4.10)

Theorem: 𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼DFA =

𝐷𝐷 𝐷𝐷 is a DFA that accepts infinitely many strings}

is decidable

Proof: The following TM decides 𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼 :

DFA On input 𝐷𝐷 , where 𝐷𝐷 is a DFA with 𝑛𝑛 states:

1. 2. 3.

Let 𝐴𝐴 be a DFA recognizing all strings of length ≥ 𝑛𝑛 Let 𝐵𝐵 be a DFA recognizing 𝐿𝐿(𝐴𝐴) ∩ 𝐿𝐿(𝐷𝐷)

Run the decider for 𝐼𝐼DFA on input 𝐵𝐵 . Accept if it rejects, and reject if it accepts.

3/18/2020 CS332 – Theory of Computation

4

Problems in Language Theory

𝑨𝑨𝐃𝐃𝐃𝐃𝐃𝐃 𝑨𝑨𝐂𝐂𝐃𝐃𝐂𝐂

𝑨𝑨𝐓𝐓𝐓𝐓

𝑬𝑬𝑬𝑬 𝐃𝐃𝐃𝐃𝐃𝐃 𝐂𝐂𝐃𝐃𝐂𝐂

𝑬𝑬? 𝐓𝐓𝐓𝐓

decidable decidable

decidable decidable ? 𝑬𝑬𝑬𝑬 𝑬𝑬𝑬𝑬 𝑬𝑬𝑬𝑬

𝐃𝐃𝐃𝐃𝐃𝐃 𝐂𝐂𝐃𝐃𝐂𝐂 𝐓𝐓𝐓𝐓

3/18/2020

decidable ? ? CS332 – Theory of Computation 5

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/17/2020 CS332 – Theory of Computation 7

Set Theory Review

A function 𝑓𝑓:𝐴𝐴 → 𝐵𝐵 is

• 1-to-1 (injective) if 𝑓𝑓 𝑎𝑎 ≠

𝑓𝑓 𝑎𝑎𝑎 forall𝑎𝑎 ≠𝑎𝑎𝑎

• 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/17/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 N, the set of natural numbers

3/17/2020 CS332 – Theory of Computation 9

Examples of countable sets

•∅

• 0,1

• 0, 1, 2, … 8675309

• 𝐼𝐼 = {2,4,6,8,…}

• 𝑆𝑆𝑆𝑆𝑆𝑆𝐴𝐴𝑆𝑆𝐼𝐼𝑆𝑆 = 1,4,9,16,25,… • 𝑃𝑃𝑃𝑃𝑃𝑃𝑃 = 1,2,4,8,16,32,…

𝐼𝐼 = 𝑆𝑆𝑆𝑆𝑆𝑆𝐴𝐴𝑆𝑆𝐼𝐼𝑆𝑆 = 𝑃𝑃𝑃𝑃𝑃𝑃𝑃 =|N|

3/17/2020 CS332 – Theory of Computation 10

How to show that N × N 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/17/2020 CS332 – Theory of Computation

11

More examples of countable sets

• {0,1} ∗

• 𝑀𝑀 𝑀𝑀 is a Turing machine} • Q = {rational numbers}

So what isn’t countable?

3/18/2020 CS332 – Theory of Computation 12

Cantor’s Diagonalization Method

Georg Cantor 1845-1918

• Invented set theory

• Defined countability, uncountability,

cardinal and ordinal numbers, …

Some praise for his work:

“Scientific charlatan…renegade…corruptor of youth” –L. Kronecker

“Set theory is wrong…utter nonsense…laughable” –L. Wittgenstein

Sylvester Medal, Royal Society, 1904

3/18/2020

CS332 – Theory of Computation 13

Uncountability of the reals

Theorem: The real interval (0, 1) is uncountable. Proof: Assume for the sake of contradiction it were

countable, and let 𝑓𝑓: N → (0,1) be a correspondence

𝑛𝑛 𝑓𝑓(𝑛𝑛)

1 0 . 𝑑𝑑 1 1 𝑑𝑑 21 𝑑𝑑 31 𝑑𝑑 41 𝑑𝑑 51 … 0 . 𝑑𝑑 12 𝑑𝑑 2 2 𝑑𝑑 32 𝑑𝑑 42 𝑑𝑑 52 … 0 . 𝑑𝑑 13 𝑑𝑑 23 𝑑𝑑 3 3 𝑑𝑑 43 𝑑𝑑 53 … 4 0 . 𝑑𝑑 14 𝑑𝑑 24 𝑑𝑑 34 𝑑𝑑 4 4 𝑑𝑑 54 …

2

3

Construct 𝑏𝑏 ∈ (0,1) which does not appear in this table – contradiction!

0 . 𝑑𝑑5 𝑑𝑑5 𝑑𝑑5 𝑑𝑑5 𝑑𝑑5 … 12345

5

𝑏𝑏=0.𝑑𝑑 𝑑𝑑 𝑑𝑑 …where𝑑𝑑 ≠digit𝑖𝑖of𝑓𝑓(𝑖𝑖) 123 𝑖𝑖

3/18/2020 CS332 – Theory of Computation 14

Uncountability of the reals

𝑛𝑛 𝑓𝑓(𝑛𝑛)

1 0.8675309… 0.1415926… 0.7182818… 0.4444444… 0.1337133…

A concrete example:

2

3

4

5

Construct 𝑏𝑏 ∈ (0,1) which does not appear in this table – contradiction!

𝑏𝑏=0.𝑑𝑑 𝑑𝑑 𝑑𝑑 …where𝑑𝑑 ≠digit𝑖𝑖of𝑓𝑓(𝑖𝑖) 123 𝑖𝑖

3/18/2020 CS332 – Theory of Computation 15

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 Q ∩ (0,1) [rational numbers in (0,1)] is uncountable?

Let 𝑓𝑓: N → Q ∩ (0,1) be a correspondence 𝑛𝑛 𝑓𝑓(𝑛𝑛)

1 0.8678678… 0.1414141… 0.7182718… 4 0.4444444… 5 0.1337133…

2

3

Construct 𝑏𝑏 ∈ (0,1) which does not appear in this table

𝑏𝑏 = 0. 𝑑𝑑1𝑑𝑑2𝑑𝑑3… where 𝑑𝑑𝑖𝑖 ≠ digit 𝑖𝑖 of 𝑓𝑓(𝑖𝑖)

3/18/2020 CS332 – Theory of Computation 17

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 𝑓𝑓: 𝑋𝑋 → 𝑃𝑃(𝑋𝑋)

𝑥𝑥𝑥𝑥 𝑥𝑥1 𝑥𝑥2 𝑥𝑥3

4

3/18/2020

CS332 – Theory of Computation 19

…

Diagonalization argument

Assume a correspondence 𝑓𝑓: 𝑋𝑋 → 𝑃𝑃(𝑋𝑋)

𝑥𝑥 𝑥𝑥1 ∈𝑓𝑓(𝑥𝑥)? 𝑥𝑥2 ∈𝑓𝑓(𝑥𝑥)? 𝑥𝑥3 ∈𝑓𝑓(𝑥𝑥)? 𝑥𝑥4 ∈𝑓𝑓(𝑥𝑥)? …

𝑥𝑥1 𝑥𝑥2 𝑥𝑥3 𝑥𝑥4

YNYY

N

Y

N

N

Y

N

Y

Y

Y

Y

N

N

Define 𝑆𝑆 by flipping the diagonal:

Put 𝑥𝑥𝑖𝑖 ∈𝑆𝑆 ⟺ 𝑥𝑥𝑖𝑖 ∉𝑓𝑓(𝑥𝑥𝑖𝑖)

3/18/2020 CS332 – Theory of Computation 20

…

Example

Let𝑋𝑋= 1,2,3,𝑃𝑃𝑋𝑋 ={∅, 1, 2, 1,2, 2,3,{1,2,3}} Ex.𝑓𝑓1 = 1,2,𝑓𝑓2 =∅, 𝑓𝑓3 ={2}

𝑥𝑥 1∈𝑓𝑓(𝑥𝑥)? 2 ∈𝑓𝑓(𝑥𝑥)? 3 ∈𝑓𝑓(𝑥𝑥)? 123

…

Construct 𝑆𝑆 =

3/18/2020 CS332 – Theory of Computation 21

…

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 𝑦𝑦 ∈ 𝑋𝑋,

𝑆𝑆 = 𝑥𝑥 ∈ 𝑋𝑋 𝑥𝑥 ∉ 𝑓𝑓(𝑥𝑥)}

then 𝑦𝑦 ∈ 𝑆𝑆 if and only if 𝑦𝑦 ∉ 𝑆𝑆

3/18/2020 CS332 – Theory of Computation 22

Undecidable Languages

3/18/2020 CS332 – Theory of Computation 23

An Existential Proof

Theorem: There exists an undecidable language over {0, 1} Proof:

A simplifying assumption: Every string in {0, 1}∗ is the encoding 𝑀𝑀 of some Turing machine 𝑀𝑀

Set of all Turing machines: 𝑋𝑋 = {0, 1}∗

Set of all languages over {0, 1} = all subsets of {0, 1}∗

There are more languages than there are TM deciders!

3/18/2020 CS332 – Theory of Computation 24

= 𝑃𝑃(𝑋𝑋)

An Existential Proof

Theorem: There exists an unrecognizable language over {0, 1} Proof:

A simplifying assumption: Every string in {0, 1}∗ is the encoding 𝑀𝑀 of some Turing machine 𝑀𝑀

Set of all Turing machines: 𝑋𝑋 = {0, 1}∗

Set of all languages over {0, 1} = all subsets of {0, 1}∗

There are more languages than there are TM recognizers! 3/18/2020 CS332 – Theory of Computation 25

= 𝑃𝑃(𝑋𝑋)

A Specific Undecidable Language

𝐴𝐴TM = 𝑀𝑀,𝑤𝑤 𝑀𝑀 is a TM that accepts input 𝑤𝑤} Theorem: 𝐴𝐴TM is undecidable

But first: 𝐴𝐴TM is Turing-recognizable

The following “universal TM” 𝑆𝑆 recognizes 𝐴𝐴TM

Oninput 𝑀𝑀,𝑤𝑤:

1. Simulate running 𝑀𝑀 on input 𝑤𝑤

2. If 𝑀𝑀 accepts, accept. If 𝑀𝑀 rejects, reject.

3/18/2020 CS332 – Theory of Computation 26

More on the Universal TM

“It is possible to invent a single machine which can be used to compute any computable sequence. If this machine U is supplied with a tape on the beginning of which is written the S.D [“standard description”] of some computing machine M, then U will compute the same sequence as M.”

– Turing, “On Computable Numbers…” 1936 • Foreshadowed general-purpose programmable computers

• No need for specialized hardware: Virtual machines as software

Harvard architecture: von Neumann architecture: Separate instruction and data pathways Programs can be treated as data

3/18/2020 CS332 – Theory of Computation 27

A Specific Undecidable Language

𝐴𝐴TM = 𝑀𝑀,𝑤𝑤 𝑀𝑀 is a TM that accepts input 𝑤𝑤} Theorem: 𝐴𝐴TM is undecidable

Proof: Assume for the sake of contradiction that TM 𝐻𝐻

decides 𝐴𝐴TM:

𝐻𝐻 𝑀𝑀,𝑤𝑤 = �

accept if 𝑀𝑀 accepts 𝑤𝑤 reject if 𝑀𝑀 does not accept 𝑤𝑤

Diagonalization: Use 𝐻𝐻 to check what 𝑀𝑀 when given as input its own description…and do the opposite

3/18/2020 CS332 – Theory of Computation 28

A Specific Undecidable Language

𝐴𝐴TM = 𝑀𝑀,𝑤𝑤 𝑀𝑀 is a TM that accepts input 𝑤𝑤} Suppose 𝐻𝐻 decides 𝐴𝐴TM

Consider the following TM 𝐷𝐷. On input 𝑀𝑀 where 𝑀𝑀 is a TM:

1. Run𝐻𝐻oninput 𝑀𝑀, 𝑀𝑀

2. If 𝐻𝐻 accepts, reject. If 𝐻𝐻 rejects, accept.

Question: What does 𝐷𝐷 do on input 𝐷𝐷 ?

3/18/2020 CS332 – Theory of Computation 29

How is this diagonalization?

TM 𝑀𝑀

𝑀𝑀1 𝑀𝑀2 𝑀𝑀3 𝑀𝑀4

3/18/2020

CS332 – Theory of Computation 30

…

How is this diagonalization?

TM𝑀𝑀 𝑀𝑀(𝑀𝑀1 )? 𝑀𝑀(𝑀𝑀2 )? 𝑀𝑀(𝑀𝑀3 )? 𝑀𝑀(𝑀𝑀4 )? …

YNYY

𝑀𝑀1 𝑀𝑀2 𝑀𝑀3 𝑀𝑀4

N

Y

N

N

Y

N

Y

Y

Y

Y

N

N

𝐷𝐷 accepts input 𝑀𝑀𝑖𝑖 ⟺ 𝑀𝑀𝑖𝑖 does not accept input 𝑀𝑀𝑖𝑖 3/18/2020 CS332 – Theory of Computation 31

…

How is this diagonalization?

TM𝑀𝑀 𝑀𝑀(𝑀𝑀1 )? 𝑀𝑀(𝑀𝑀2 )? 𝑀𝑀(𝑀𝑀3 )? 𝑀𝑀(𝑀𝑀4 )? 𝐷𝐷(𝐷𝐷)?

𝑀𝑀1 𝑀𝑀2 𝑀𝑀3 𝑀𝑀4

YNYY

N

Y

N

N

Y

N

Y

Y

Y

Y

N

N

…

𝐷𝐷

𝐷𝐷 accepts input 𝑀𝑀𝑖𝑖 ⟺ 𝑀𝑀𝑖𝑖 does not accept input 𝑀𝑀𝑖𝑖

3/18/2020 CS332 – Theory of Computation 32

…

3/18/2020 CS332 – Theory of Computation 33

𝐴𝐴TM = 𝑀𝑀,𝑤𝑤

𝑀𝑀 is a TM that accepts input 𝑤𝑤} 1. Simulate running 𝑀𝑀 on input 𝑤𝑤

Oninput 𝑀𝑀,𝑤𝑤:

2. If 𝑀𝑀 accepts, accept. If 𝑀𝑀 rejects, reject.

3/18/2020 CS332 – Theory of Computation 34