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

BU CS 332 – Theory of Computation

Lecture 16:

• Mapping Reducibility

Reading: Sipser Ch 5.3

Mark Bun March 25, 2020

Problems in language theory

3/30/2020

CS332 ‐ Theory of Computation

2

𝐃𝐅𝐀

𝐂𝐅𝐆

𝐓𝐌

decidable

decidable

undecidable 𝐓𝐌

𝐃𝐅𝐀

𝐂𝐅𝐆

decidable

decidable

undecidable 𝐓𝐌

decidable

?

?

𝐃𝐅𝐀

𝐂𝐅𝐆

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

3

Reminder: Using reductions to prove undecidability

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/30/2020 CS332 ‐ Theory of Computation 4

Equality 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 TMs , as follows:

2. Run on input

3. If accepts, accept. Otherwise, reject.

3/30/2020 CS332 ‐ Theory of Computation

This is a reduction from

to 5

Equality Testing for TMs

Theorem: is undecidable

Proof: Suppose for contradiction that there exists a decider

for . We construct a decider for On input :

1. Construct TMs , as follows:

as follows:

= =

2. Run on input

3. If accepts, accept. Otherwise, reject.

3/30/2020 CS332 ‐ Theory of Computation

This is a reduction from

to 6

Problems in language theory

3/30/2020

CS332 ‐ Theory of Computation

7

𝐃𝐅𝐀

𝐂𝐅𝐆

𝐓𝐌

decidable

decidable

undecidable 𝐓𝐌

𝐃𝐅𝐀

𝐂𝐅𝐆

decidable

decidable

undecidable

decidable

?

undecidable

𝐃𝐅𝐀

𝐂𝐅𝐆

𝐓𝐌

Context‐free 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 on input

3. If accepts, accept. Otherwise, reject

3/30/2020 CS332 ‐ Theory of Computation

This is a reduction from

to 8

Context‐free language testing for TMs

Theorem: is undecidable

Proof: Suppose for contradiction that there exists a decider

for . We construct a decider for On input :

1. Construct a TM as follows:

as follows:

2. Run 3. If

3. If accepts, accept.” on input

=“Oninput , 1. If

accept

2. Run TM on input

accepts, accept. Otherwise, reject

This is a reduction from

to 9

3/30/2020 CS332 ‐ Theory of Computation

Mapping Reductions

3/30/2020 CS332 ‐ Theory of Computation 10

🚩🚩Warning🚩🚩

What’s wrong with the following “proof”?

Bogus “Theorem”: is not Turing‐recognizable

Bogus “Proof”: Suppose for contradiction that there exists a

recognizer for . We construct a recognizer for :

On input :

1. Run on input

2. If accepts, reject. Otherwise, accept.

This sure looks like a reduction from to 3/30/2020 CS332 ‐ Theory of Computation

11

Mapping Reductions: Motivation

1. How do we formalize the notion of a reduction?

2. How do we use reductions to show that languages are unrecognizable?

3. How do we protect ourselves from accidentally “proving” bogus theorems about recognizability?

3/30/2020 CS332 ‐ Theory of Computation 12

Computable Functions

Definition:

A function ∗ ∗ is computable if there is a TM which, given as input any ∗, halts with only on its tape.

Example 1:

Example 2:

= where is a TM, is a

is a TM that ignores its input and simulates

string, and running on

3/30/2020

CS332 ‐ Theory of Computation 13

Mapping Reductions

Definition:

Language is mapping reducible to language , written

if there is a computable function ∗ ∗ such that for all strings ∗, we have

3/30/2020 CS332 ‐ Theory of Computation 14

Decidability

Theorem: If and is decidable, then is also decidable

Proof: Let be a decider for mapping reduction from to as follows:

and let ∗ ∗ be a . Construct a decider for

On input : 1. Compute

2. Run 3. If

on input

accepts, accept. Otherwise, reject.

3/30/2020

CS332 ‐ Theory of Computation 15

Undecidability

Theorem: If decidable

and is decidable, then

and is undecidable, then

is also

is also

Corollary: If undecidable

3/30/2020

CS332 ‐ Theory of Computation

16

Old Proof: Equality 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 TMs , =“Oninput𝑥,

as follows:

= “Oninput𝑥,

2. Run 3. If

on input

accepts, accept. Otherwise, reject.

1. 2. 3.

Ignore 𝑥

Run 𝑀 on input 𝑤

If 𝑀 accepts, accept. Otherwise, reject.”

1. Ignore 𝑥 and accept”

3/30/2020 CS332 ‐ Theory of Computation

This is a reduction from

to 17

New Proof: Equality Testing for TMs

Theorem: hence is undecidable

Proof: The following TM computes the reduction: On input :

1.

Construct TMs ,

as follows:

= “Oninput𝑥,

=“Oninput𝑥,

1. Ignore 𝑥

2. Run 𝑀 on input 𝑤

3. If 𝑀 accepts, accept.

1. Ignore 𝑥 and accept”

2. Output 3/30/2020

Otherwise, reject.”

CS332 ‐ Theory of Computation 18

Mapping Reductions: Recognizability

Theorem: If and is recognizable, then is also recognizable

Proof: Let be a recognizer for and let ∗ ∗ be a mapping reduction from to . Construct a recognizer for as follows:

On input : 1. Compute

2. Run 3. If

on input

accepts, accept. Otherwise, reject.

3/30/2020

CS332 ‐ Theory of Computation 19

Unrecognizability

Theorem: If and is recognizable, then recognizable

is also

Corollary: If and is unrecognizable, then also unrecognizable

is

Corollary: If 3/30/2020

, then is unrecognizable

CS332 ‐ Theory of Computation

20

Recognizability and

3/30/2020 CS332 ‐ Theory of Computation 21

Consequences of

1. Since

is undecidable,

implies

is also undecidable

2. Since

is unrecognizable,

is unrecognizable

3/30/2020

CS332 ‐ Theory of Computation 22

itself is also unrecognizable

Theorem: 𝐴 hence is unrecognizable

Proof: The following TM computes the reduction: On input :

1.

Construct TMs ,

as follows:

= “Oninput𝑥,

=“Oninput𝑥,

1. Ignore 𝑥

2. Run 𝑀 on input 𝑤

3. If 𝑀 accepts, accept.

1. Ignore 𝑥 and accept”

2. Output 3/30/2020

Otherwise, reject.”

CS332 ‐ Theory of Computation 23

More on Reductions and Undecidability

3/30/2020 CS332 ‐ Theory of Computation 24

Problems in language theory

3/30/2020

CS332 ‐ Theory of Computation

25

𝐃𝐅𝐀

𝐂𝐅𝐆

𝐓𝐌

decidable

decidable

undecidable 𝐓𝐌

𝐃𝐅𝐀

𝐂𝐅𝐆

decidable

decidable

undecidable

decidable

?

undecidable

𝐃𝐅𝐀

𝐂𝐅𝐆

𝐓𝐌

On input :

1. Construct a CFG

such that:

does not accept

2. Output 3/30/2020

CS332 ‐ Theory of Computation 26

is undecidable

∗

Theorem: hence is undecidable Proof idea: “Computation history method”

∗

Problems in language theory

3/30/2020

CS332 ‐ Theory of Computation 27

𝐃𝐅𝐀

𝐂𝐅𝐆 𝐓𝐌

decidable

undecidable 𝐂𝐅𝐆 𝐓𝐌

𝐃𝐅𝐀

decidable decidable

decidable

undecidable 𝐂𝐅𝐆 𝐓𝐌

decidable

undecidable undecidable

𝐃𝐅𝐀

Undecidable problems outside language theory

Post Correspondence Problem (PCP):

Domino: . Top and bottom are strings.

Input: Collection of dominos.

Match: List of some of the input dominos (repetitions allowed) where top = bottom

Problem: Does a match exist? This is undecidable 3/30/2020 CS332 ‐ Theory of Computation 28