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