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