# 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

𝑨𝑨𝐃𝐃𝐃𝐃𝐃𝐃 𝑨𝑨𝐂𝐂𝐃𝐃𝐂𝐂 𝑨𝑨𝐓𝐓𝐓𝐓

undecidable 𝑬𝑬𝑬𝑬𝑬𝑬

decidable decidable

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

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

decidable decidable undecidable

𝐓𝐓𝐓𝐓

3/24/2020

decidable ? ? CS332 – Theory of Computation

2

Reductions

A reduction from problem 𝐴𝐴 to problem 𝐵𝐵 is an algorithm for problem 𝐴𝐴 which uses an algorithm for problem 𝐵𝐵 as a subroutine

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

3/24/2020 CS332 – Theory of Computation 3

Reminder: Using reductions to prove undecidability

If 𝐴𝐴 reduces to 𝐵𝐵 and 𝐴𝐴 is undecidable, then 𝐵𝐵 is also undecidable

Suppose to the contrary that 𝐵𝐵 is decidable Using 𝐵𝐵 as a subroutine, construct an algorithm

Proof template:

1. 2.

3.

deciding 𝐴𝐴

But 𝐴𝐴 is undecidable. Contradiction!

3/24/2020 CS332 – Theory of Computation 4

Equality Testing for TMs

𝐸𝐸𝐸𝐸TM= 𝑀𝑀1,𝑀𝑀2 𝑀𝑀1,𝑀𝑀2areTMsand𝐿𝐿𝑀𝑀1 =𝐿𝐿𝑀𝑀2 } Theorem: 𝐸𝐸𝐸𝐸TM is undecidable

Proof: Suppose for contradiction that there exists a decider 𝑅𝑅 for 𝐸𝐸𝐸𝐸TM. We construct a decider for 𝐴𝐴TM as follows:

Oninput 𝑀𝑀,𝑤𝑤:

1. Construct TMs 𝑀𝑀1, 𝑀𝑀2 as follows:

2.Run𝑅𝑅oninput 𝑀𝑀1,𝑀𝑀2

3. If 𝑅𝑅 accepts, accept. Otherwise, reject.

This is a reduction from 𝐴𝐴TM to 𝐸𝐸𝐸𝐸TM 3/24/2020 CS332 – Theory of Computation 5

Equality Testing for TMs

𝐸𝐸𝐸𝐸TM= 𝑀𝑀1,𝑀𝑀2 𝑀𝑀1,𝑀𝑀2areTMsand𝐿𝐿𝑀𝑀1 =𝐿𝐿𝑀𝑀2 } Theorem: 𝐸𝐸𝐸𝐸TM is undecidable

Proof: Suppose for contradiction that there exists a decider 𝑅𝑅 for 𝐸𝐸𝐸𝐸TM. We construct a decider for 𝐴𝐴TM as follows:

Oninput 𝑀𝑀,𝑤𝑤:

1. Construct TMs 𝑀𝑀1, 𝑀𝑀2 as follows:

𝑀𝑀1 = 𝑀𝑀2 =

2.Run𝑅𝑅oninput 𝑀𝑀1,𝑀𝑀2

3. If 𝑅𝑅 accepts, accept. Otherwise, reject.

This is a reduction from 𝐴𝐴TM to 𝐸𝐸𝐸𝐸TM 3/25/2020 CS332 – Theory of Computation 6

Problems in language theory

𝑨𝑨𝐃𝐃𝐃𝐃𝐃𝐃 𝑨𝑨𝐂𝐂𝐃𝐃𝐂𝐂 𝑨𝑨𝐓𝐓𝐓𝐓

𝑬𝑬𝑬𝑬𝑬𝑬 𝐃𝐃𝐃𝐃𝐃𝐃 𝐂𝐂𝐃𝐃𝐂𝐂 𝐓𝐓𝐓𝐓

decidable decidable

undecidable

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

decidable decidable undecidable

𝐓𝐓𝐓𝐓

3/25/2020

decidable ? undecidable CS332 – Theory of Computation

7

Context-free language testing for TMs

𝐶𝐶𝐶𝐶𝐿𝐿TM = 𝑀𝑀 𝑀𝑀isaTMand𝐿𝐿 𝑀𝑀 iscontextfree} Theorem: 𝐶𝐶𝐶𝐶𝐿𝐿TM is undecidable

Proof: Suppose for contradiction that there exists a decider 𝑅𝑅 for 𝐶𝐶𝐶𝐶𝐿𝐿TM. We construct a decider for 𝐴𝐴TM as follows:

Oninput 𝑀𝑀,𝑤𝑤:

1. Construct a TM 𝑀𝑀𝑀 as follows:

2.Run𝑅𝑅oninput 𝑀𝑀′

3. If 𝑅𝑅 accepts, accept. Otherwise, reject

This is a reduction from 𝐴𝐴TM to 𝐶𝐶𝐶𝐶𝐿𝐿TM 3/24/2020 CS332 – Theory of Computation 8

Context-free language testing for TMs

𝐶𝐶𝐶𝐶𝐿𝐿TM = 𝑀𝑀 𝑀𝑀isaTMand𝐿𝐿 𝑀𝑀 iscontextfree} Theorem: 𝐶𝐶𝐶𝐶𝐿𝐿TM is undecidable

Proof: Suppose for contradiction that there exists a decider 𝑅𝑅 for 𝐶𝐶𝐶𝐶𝐿𝐿TM. We construct a decider for 𝐴𝐴TM as follows:

Oninput 𝑀𝑀,𝑤𝑤:

1. Construct a TM 𝑀𝑀𝑀 as follows:

𝑀𝑀𝑀 = “On input 𝑥𝑥,

1.If𝑥𝑥∈ 0𝑛𝑛1𝑛𝑛2𝑛𝑛 𝑛𝑛≥0},accept 2. Run TM 𝑀𝑀 on input 𝑤𝑤

3. If 𝑀𝑀 accepts, accept.”

2.Run𝑅𝑅oninput 𝑀𝑀′

3. If 𝑅𝑅 accepts, accept. Otherwise, reject

This is a reduction from 𝐴𝐴TM to 𝐶𝐶𝐶𝐶𝐿𝐿TM 3/24/2020 CS332 – Theory of Computation 9

Mapping Reductions

3/24/2020 CS332 – Theory of Computation 10

🚩🚩🚩🚩Warning🚩🚩🚩🚩

What’s wrong with the following “proof”?

Bogus “Theorem”: 𝐴𝐴 is not Turing-recognizable

recognizer 𝑅𝑅 for 𝐴𝐴

TM

. We construct a recognizer for 𝐴𝐴 1. Run 𝑅𝑅 on input 𝑀𝑀,𝑤𝑤

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

TM

2. If 𝑅𝑅 accepts, reject. Otherwise, accept.

TM

:

Oninput 𝑀𝑀,𝑤𝑤:

This sure looks like a reduction from 𝐴𝐴TM to 𝐴𝐴TM 3/24/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/24/2020 CS332 – Theory of Computation 12

Computable Functions

A function 𝑓𝑓: Σ∗ → Σ∗ is computable if there is a TM 𝑀𝑀 which, given as input any 𝑤𝑤 ∈ Σ∗, halts with only 𝑓𝑓(𝑤𝑤) on its tape.

Definition:

Example1:𝑓𝑓 𝑥𝑥,𝑦𝑦 =𝑥𝑥+𝑦𝑦

Example2:𝑓𝑓 𝑀𝑀,𝑤𝑤 = 𝑀𝑀′ where𝑀𝑀isaTM,𝑤𝑤isa string, and 𝑀𝑀𝑀 is a TM that ignores its input and simulates running 𝑀𝑀 on 𝑤𝑤

3/24/2020 CS332 – Theory of Computation 13

Mapping Reductions

Definition:

Language 𝐴𝐴 is mapping reducible to language 𝐵𝐵, written

𝐴𝐴 ≤m 𝐵𝐵

if there is a computable function 𝑓𝑓: Σ∗ → Σ∗ such that for

all strings 𝑤𝑤 ∈ Σ∗, we have 𝑤𝑤 ∈ 𝐴𝐴 ⟺ 𝑓𝑓(𝑤𝑤) ∈ 𝐵𝐵

3/25/2020 CS332 – Theory of Computation 14

Decidability

Theorem: If 𝐴𝐴 ≤m 𝐵𝐵 and 𝐵𝐵 is decidable, then 𝐴𝐴 is also decidable

Proof:Let𝑀𝑀beadeciderfor𝐵𝐵andlet𝑓𝑓:Σ∗ →Σ∗ bea mapping reduction from 𝐴𝐴 to 𝐵𝐵. Construct a decider for 𝐴𝐴 as follows:

On input 𝑤𝑤:

1. Compute 𝑓𝑓(𝑤𝑤)

2. Run 𝑀𝑀 on input 𝑓𝑓(𝑤𝑤)

3. If 𝑀𝑀 accepts, accept. Otherwise, reject.

3/24/2020 CS332 – Theory of Computation 15

Undecidability

Theorem: If 𝐴𝐴 ≤m 𝐵𝐵 and 𝐵𝐵 is decidable, then 𝐴𝐴 is also decidable

Corollary: If 𝐴𝐴 ≤m 𝐵𝐵 and 𝐴𝐴 is undecidable, then 𝐵𝐵 is also undecidable

3/24/2020 CS332 – Theory of Computation 16

𝐸𝐸𝐸𝐸 =𝑀𝑀,𝑀𝑀 𝑀𝑀,𝑀𝑀areTMsand𝐿𝐿𝑀𝑀=𝐿𝐿𝑀𝑀} TM1212 12

Old Proof: Equality Testing for TMs

Theorem: 𝐸𝐸𝐸𝐸TM is undecidable

Proof: Suppose for contradiction that there exists a decider 𝑅𝑅

for 𝐸𝐸𝐸𝐸TM. We construct a decider for 𝐴𝐴TM as follows: Oninput 𝑀𝑀,𝑤𝑤:

1. Construct TMs 𝑀𝑀1, 𝑀𝑀2 as follows:

𝑀𝑀1 = “On input 𝑥𝑥, 𝑀𝑀2 = “On input 𝑥𝑥,

1. Ignore 𝑥𝑥 1. Ignore 𝑥𝑥 and accept” 2. Run 𝑀𝑀 on input 𝑤𝑤

3. If 𝑀𝑀 accepts, accept.

Otherwise, reject.” 2.Run𝑅𝑅oninput 𝑀𝑀 ,𝑀𝑀

12

3. If 𝑅𝑅 accepts, accept. Otherwise, reject.

This is a reduction from 𝐴𝐴TM to 𝐸𝐸𝐸𝐸TM 3/25/2020 CS332 – Theory of Computation 17

𝐸𝐸𝐸𝐸 =𝑀𝑀,𝑀𝑀 𝑀𝑀,𝑀𝑀areTMsand𝐿𝐿𝑀𝑀=𝐿𝐿𝑀𝑀} TM1212 12

New Proof: Equality Testing for TMs

Theorem: 𝐴𝐴TM ≤m 𝐸𝐸𝐸𝐸TM hence 𝐸𝐸𝐸𝐸TM is undecidable Proof: The following TM computes the reduction:

Oninput 𝑀𝑀,𝑤𝑤:

1. Construct TMs 𝑀𝑀1, 𝑀𝑀2 as follows:

𝑀𝑀1 = “On input 𝑥𝑥, 𝑀𝑀2 = “On input 𝑥𝑥,

1. Ignore 𝑥𝑥 1. Ignore 𝑥𝑥 and accept” 2. Run 𝑀𝑀 on input 𝑤𝑤

3. If 𝑀𝑀 accepts, accept.

Otherwise, reject.” 2.Output 𝑀𝑀,𝑀𝑀

12

3/25/2020 CS332 – Theory of Computation 18

Mapping Reductions: Recognizability

Theorem: If 𝐴𝐴 ≤m 𝐵𝐵 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 𝑀𝑀 on input 𝑓𝑓(𝑤𝑤)

3. If 𝑀𝑀 accepts, accept. Otherwise, reject.

3/25/2020 CS332 – Theory of Computation 19

Unrecognizability

Theorem: If 𝐴𝐴 ≤m 𝐵𝐵 and 𝐵𝐵 is recognizable, then 𝐴𝐴 is also recognizable

Corollary: If 𝐴𝐴 ≤m 𝐵𝐵 and 𝐴𝐴 is unrecognizable, then 𝐵𝐵 is also unrecognizable

Corollary: If 𝐴𝐴TM ≤m 𝐵𝐵, then 𝐵𝐵 is unrecognizable

3/25/2020 CS332 – Theory of Computation 20

Recognizability and 𝐴𝐴TM

3/25/2020 CS332 – Theory of Computation 21

Consequences of 𝐴𝐴TM ≤m 𝐸𝐸𝐸𝐸TM

1. Since 𝐴𝐴TM is undecidable, 𝐸𝐸𝐸𝐸TM is also undecidable

2. 𝐴𝐴TM ≤m 𝐸𝐸𝐸𝐸TM implies 𝐴𝐴TM ≤m 𝐸𝐸𝐸𝐸TM

Since 𝐴𝐴TM is unrecognizable, 𝐸𝐸𝐸𝐸TM is unrecognizable

3/25/2020 CS332 – Theory of Computation 22

𝐸𝐸𝐸𝐸TM itself is also unrecognizable

𝐸𝐸𝐸𝐸TM= 𝑀𝑀1,𝑀𝑀2 𝑀𝑀1,𝑀𝑀2areTMsand𝐿𝐿𝑀𝑀1 =𝐿𝐿𝑀𝑀2 } Theorem: 𝐴𝐴TM ≤m 𝐸𝐸𝐸𝐸TM hence 𝐸𝐸𝐸𝐸TM is unrecognizable Proof: The following TM computes the reduction:

Oninput 𝑀𝑀,𝑤𝑤:

1. Construct TMs 𝑀𝑀1, 𝑀𝑀2 as follows:

𝑀𝑀1 = “On input 𝑥𝑥, 𝑀𝑀2 = “On input 𝑥𝑥,

1. 2. 3.

Ignore 𝑥𝑥 1. Ignore 𝑥𝑥 and accept” Run 𝑀𝑀 on input 𝑤𝑤

If 𝑀𝑀 accepts, accept.

Otherwise, reject.”

CS332 – Theory of Computation 23

2.Output 𝑀𝑀,𝑀𝑀 3/25/2020 1 2

More on Reductions and Undecidability

3/25/2020 CS332 – Theory of Computation 24

Problems in language theory

𝑨𝑨𝐃𝐃𝐃𝐃𝐃𝐃 𝑨𝑨𝐂𝐂𝐃𝐃𝐂𝐂 𝑨𝑨𝐓𝐓𝐓𝐓

𝑬𝑬𝑬𝑬𝑬𝑬 𝐃𝐃𝐃𝐃𝐃𝐃 𝐂𝐂𝐃𝐃𝐂𝐂 𝐓𝐓𝐓𝐓

decidable decidable

undecidable

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

decidable decidable undecidable

𝐓𝐓𝐓𝐓

3/25/2020

decidable ? undecidable CS332 – Theory of Computation

25

𝐴𝐴𝐿𝐿𝐿𝐿CFG is undecidable

𝐴𝐴𝐿𝐿𝐿𝐿CFG = 𝐺𝐺 𝐺𝐺 is a CFG with terminal set Σ

and𝐿𝐿𝐺𝐺 =Σ∗}

Theorem: 𝐴𝐴TM ≤m 𝐸𝐸𝐸𝐸CFG hence 𝐸𝐸𝐸𝐸CFG is undecidable

Proof idea: “Computation history method” Oninput 𝑀𝑀,𝑤𝑤:

1. Construct a CFG 𝐺𝐺 such that:

𝐿𝐿 𝐺𝐺 =Σ∗ ⟺ 𝑀𝑀doesnotaccept𝑤𝑤

2.Output 𝐺𝐺

3/25/2020 CS332 – Theory of Computation 26

Problems in language theory

𝑨𝑨𝐃𝐃𝐃𝐃𝐃𝐃 𝑨𝑨𝐂𝐂𝐃𝐃𝐂𝐂 𝑨𝑨𝐓𝐓𝐓𝐓

undecidable 𝑬𝑬𝑬𝑬𝑬𝑬

decidable decidable

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

decidable decidable undecidable 𝑬𝑬𝑬𝑬 𝑬𝑬𝑬𝑬 𝑬𝑬𝑬𝑬

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

3/25/2020

decidable undecidable undecidable CS332 – Theory of Computation

27

Undecidable problems outside language theory

𝑎𝑎

Domino: 𝑎𝑎𝑎𝑎 . Top and bottom are strings.

Post Correspondence Problem (PCP):

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