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