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

BU CS 332 – Theory of Computation

Lecture 15:

• Undecidable and Unrecognizable Languages

Reading:

Sipser Ch 4.2, 5.1

• Reductions

Mark Bun March 23, 2020

How can we compare sizes of infinite sets?

Definition: Two sets have the same size if there is a correspondence (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/23/2020 CS332 ‐ Theory of Computation 2

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: Use diagonalization to construct a set that cannot be the output for any

3/23/2020 CS332 ‐ Theory of Computation 3

Undecidable Languages

3/23/2020 CS332 ‐ Theory of Computation 4

Problems in language theory

3/23/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/23/2020 CS332 ‐ Theory of Computation 6

An existential proof

Theorem: There exists an undecidable language over Proof:

A simplifying assumption: Every string in encoding of some Turing machine

∗ is the ∗

Set of all Turing machines:

Set of all languages over :

∗

There are more languages than there are TM deciders!

3/23/2020 CS332 ‐ Theory of Computation 7

all subsets of =

An existential proof

Theorem: There exists an unrecognizable language over Proof:

A simplifying assumption: Every string in encoding of some Turing machine

∗ is the ∗

Set of all Turing machines:

Set of all languages over :

∗

There are more languages than there are TM recognizers! 3/23/2020 CS332 ‐ Theory of Computation 8

all subsets of =

…

An explicit undecidable language

TM 𝑀

𝑀 𝑀 𝑀 𝑀

3/23/2020

CS332 ‐ Theory of Computation 9

…

An explicit undecidable language

TM𝑀 𝑀𝑀 ? 𝑀𝑀 ? 𝑀𝑀 ? 𝑀𝑀 ?

𝐷 𝐷 ?

𝑀 𝑀 𝑀 𝑀

Y N Y Y … NNYY

𝐷

3/23/2020

CS332 ‐ Theory of Computation 10

YYYN NNYN

Suppose decides

An explicit undecidable language

Theorem:

is undecidable

Proof: Suppose for contradiction, that

decides

Corollary:

is undecidable

3/23/2020 CS332 ‐ Theory of Computation

11

A more useful undecidable language

Theorem: is undecidable

But first: is Turing‐recognizable

The following “universal TM” recognizes

On input :

1. Simulate running on input

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

3/23/2020 CS332 ‐ Theory of Computation

12

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/23/2020 CS332 ‐ Theory of Computation 13

A more useful undecidable language

Theorem: is undecidable

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

Idea: Show that can be used to decide the (undecidable) language ‐‐ a contradiction.

3/23/2020 CS332 ‐ Theory of Computation 14

A more useful undecidable language

Suppose decides

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

1. Run

2. If

on input

accepts, accept. If rejects, reject.

Claim:

decides

3/23/2020

CS332 ‐ Theory of Computation 15

…but this language is undecidable

Unrecognizable Languages

Theorem: A language is decidable if and only if and are both Turing‐recognizable.

Proof:

3/23/2020 CS332 ‐ Theory of Computation

16

Classes of Languages

recognizable

decidable context free

regular

3/23/2020 CS332 ‐ Theory of Computation 17

Reductions

3/23/2020 CS332 ‐ Theory of Computation 18

A more useful undecidable language

Theorem: is undecidable

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

Idea: Show that can be used to decide the (undecidable) language ‐‐ a contradiction.

“A reduction from to ” 3/23/2020 CS332 ‐ Theory of Computation

19

Scientists vs. Engineers

A computer scientist and an engineer are stranded on a desert island. They find two palm trees with one coconut on each. The engineer climbs a tree, picks a coconut and eats.

The computer scientist climbs the second tree, picks a coconut, climbs down, climbs up the first tree and places it there, declaring success.

“Now we’ve reduced the problem to one we’ve already solved.”

3/23/2020 CS332 ‐ Theory of Computation 20

Reductions

A reduction from problem to problem is an algorithm

for problem which uses an algorithm for problem subroutine

as a

If such a reduction exists, we say “ reduces to ”

3/23/2020 CS332 ‐ Theory of Computation

21

Two uses of reductions

Positive uses: If reduces to and is decidable, then is also decidable

Theorem: is decidable

Proof: The following TM decides

On input , where are DFAs:

1. Construct a DFA that recognizes the symmetric

difference

2. Run the decider for on and return its output 3/23/2020 CS332 ‐ Theory of Computation 22

Two uses of reductions

Negative uses: If reduces to and is undecidable, then is also undecidable

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

Consider the following TM 𝐷.

On input 𝑀 where 𝑀 is a TM:

1. Run𝐻oninput 𝑀, 𝑀

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

Claim: 𝐷 decides

𝑆𝐴 𝑀 𝑀 is a TM that accepts on input 𝑀

3/23/2020 CS332 ‐ Theory of Computation

23

Two uses of reductions

Negative uses: If reduces to and is undecidable, then is also undecidable

Proof template:

1. 2.

Suppose to the contrary that is decidable

3.

But is undecidable. Contradiction!

Using as a subroutine, construct an algorithm deciding

3/23/2020 CS332 ‐ Theory of Computation 24

Halting Problem

for

On input 1. Run 2. If

3. If

4. If

. We construct a decider for as follows: :

3/23/2020

CS332 ‐ Theory of Computation

is undecidable

Proof: Suppose for contradiction that there exists a decider

Theorem:

on input

rejects, reject

accepts, simulate on

accepts, accept. Otherwise, reject This is a reduction from

to 25

Empty language testing for TMs

Theorem: is undecidable

Proof: Suppose for contradiction that there exists a decider for . We construct a decider for as follows:

On input 1. Run

:

on input ???

3/23/2020

CS332 ‐ Theory of Computation

26

This is a reduction from to

Empty language testing for TMs

Theorem: is undecidable

Proof: Suppose for contradiction that there exists a decider for . We construct a decider for as follows:

On input :

1. Construct a TM as follows:

2. Run 3. If

on input

, accept. Otherwise, reject

3/23/2020

CS332 ‐ Theory of Computation

This is a reduction from

to 27