PowerPoint Presentation
BU CS 332 – Theory of Computation
Lecture 18:
• More Mapping Reductions
• Computation History
Method
Reading:
Sipser Ch 5.3, 5.1
Mark Bun
March 24, 2021
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/24/2021 CS332 – Theory of Computation 2
Mapping Reductions: Implications
Theorem:
If 𝐴𝐴 ≤m 𝐵𝐵 and 𝐵𝐵 is decidable (resp. recognizable), then 𝐴𝐴 is
also decidable (resp. recognizable)
Corollary:
If 𝐴𝐴 ≤m 𝐵𝐵 and 𝐴𝐴 is undecidable (resp. unrecognizable),
then 𝐵𝐵 is also undecidable (resp. unrecognizable)
3/24/2021 CS332 – Theory of Computation 3
Example: Another reduction to 𝐸𝐸𝐸𝐸TM
3/24/2021 CS332 – Theory of Computation 4
𝐸𝐸𝐸𝐸TM = 𝑀𝑀1,𝑀𝑀2 𝑀𝑀1,𝑀𝑀2 are TMs and 𝐿𝐿 𝑀𝑀1 = 𝐿𝐿 𝑀𝑀2 }
Theorem: 𝐴𝐴TM ≤m 𝐸𝐸𝐸𝐸TM
Proof: The following TM 𝑁𝑁 computes the reduction 𝑓𝑓:
What should the inputs and outputs to 𝑓𝑓 be?
a) 𝑓𝑓 should take as input a pair 𝑀𝑀1,𝑀𝑀2 and output a pair 〈𝑀𝑀,𝑤𝑤〉
b) 𝑓𝑓 should take as input a pair 〈𝑀𝑀,𝑤𝑤〉 and output a pair 𝑀𝑀1,𝑀𝑀2
c) 𝑓𝑓 should take as input a pair 𝑀𝑀1,𝑀𝑀2 and either accept or reject
d) 𝑓𝑓 should take as input a pair 〈𝑀𝑀,𝑤𝑤〉 and either accept or reject
Example: Another reduction to 𝐸𝐸𝐸𝐸TM
3/24/2021 CS332 – Theory of Computation 5
𝐸𝐸𝐸𝐸TM = 𝑀𝑀1,𝑀𝑀2 𝑀𝑀1,𝑀𝑀2 are TMs and 𝐿𝐿 𝑀𝑀1 = 𝐿𝐿 𝑀𝑀2 }
Theorem: 𝐴𝐴TM ≤m 𝐸𝐸𝐸𝐸TM
Proof: The following TM 𝑁𝑁 computes the reduction 𝑓𝑓:
On input 𝑀𝑀,𝑤𝑤 :
1. Construct TMs 𝑀𝑀1, 𝑀𝑀2 as follows:
𝑀𝑀1 = “On input 𝑥𝑥, 𝑀𝑀2 = “On input 𝑥𝑥,
2. Output 𝑀𝑀1,𝑀𝑀2
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/24/2021 CS332 – Theory of Computation 6
𝐸𝐸𝐸𝐸TM itself is also unrecognizable
3/24/2021 CS332 – Theory of Computation 7
𝐸𝐸𝐸𝐸TM = 𝑀𝑀1,𝑀𝑀2 𝑀𝑀1,𝑀𝑀2 are TMs and 𝐿𝐿 𝑀𝑀1 = 𝐿𝐿 𝑀𝑀2 }
Theorem: 𝐴𝐴TM ≤m 𝐸𝐸𝐸𝐸TM hence 𝐸𝐸𝐸𝐸TM is unrecognizable
Proof: The following TM computes the reduction:
On input 𝑀𝑀,𝑤𝑤 :
1. Construct TMs 𝑀𝑀1, 𝑀𝑀2 as follows:
𝑀𝑀1 = “On input 𝑥𝑥, 𝑀𝑀2 = “On input 𝑥𝑥,
1. Ignore 𝑥𝑥 1. Ignore 𝑥𝑥 and reject”
2. Run 𝑀𝑀 on input 𝑤𝑤
3. If 𝑀𝑀 accepts, accept.
Otherwise, reject.”
2. Output 𝑀𝑀1,𝑀𝑀2
Computation History
Method
3/24/2021 CS332 – Theory of Computation 8
Problems in Language Theory
Apparent dichotomy:
• TMs seem to be able to
solve problems about the
power of weaker
computational models
(e.g., DFAs)
• TMs can’t solve problems
about the power of TMs
themselves
Question: Are there
undecidable problems that
do not involve TM
descriptions?
3/24/2021 CS332 – Theory of Computation 9
𝑨𝑨𝐃𝐃𝐃𝐃𝐃𝐃
decidable
𝑬𝑬𝐃𝐃𝐃𝐃𝐃𝐃
decidable
𝑬𝑬𝑬𝑬𝐃𝐃𝐃𝐃𝐃𝐃
decidable
𝑨𝑨𝐓𝐓𝐓𝐓
undecidable
𝑬𝑬𝐓𝐓𝐓𝐓
undecidable
𝑬𝑬𝑬𝑬𝐓𝐓𝐓𝐓
undecidable
Linear Bounded Automata (LBA)
A linear bounded automaton (LBA) is a TM variant with a
bounded tape. The number of tape cells is the length of
the input.
3/24/2021 CS332 – Theory of Computation 10
Tape 𝑎𝑎 𝑏𝑏 𝑎𝑎 𝑎𝑎 𝑏𝑏 𝑎𝑎
Finite
control
Input
Intermediate in power between DFAs and TMs:
Regular langs. SPACE 𝑛𝑛 Turing-recognizable langs.
Configurations
3/24/2021 CS332 – Theory of Computation 11
A configuration is a string 𝑢𝑢𝑢𝑢𝑢𝑢 where 𝑢𝑢 ∈ 𝐸𝐸 and 𝑢𝑢, 𝑢𝑢 ∈ Γ∗
• Tape contents = 𝑢𝑢𝑢𝑢
• Current state = 𝑢𝑢
• Tape head on first symbol of 𝑢𝑢
1 0 1 0 1 1 1 ⊔
𝑢𝑢5
Ex. 101𝑢𝑢50111 ⊔
Computing with Configurations
A sequence of configurations 𝐶𝐶0, … ,𝐶𝐶ℓ is an accepting
computation history for TM (or LBA) 𝑀𝑀 on input 𝑤𝑤 if
1. 𝐶𝐶0 is the start configuration 𝑢𝑢0𝑤𝑤1 …𝑤𝑤𝑛𝑛
2. Every 𝐶𝐶𝑖𝑖+1 legally follows from 𝐶𝐶𝑖𝑖
3. 𝐶𝐶ℓ is an accepting configuration
Rejecting computation history: Same thing, but 𝐶𝐶ℓ is a
rejecting configuration
If 𝑀𝑀 loops on 𝑤𝑤, there is no accepting or rejecting
computation history
3/24/2021 CS332 – Theory of Computation 12
Counting Configurations
How many distinct configurations are possible for an LBA
with 𝑘𝑘 states, 𝑎𝑎 symbols in its tape alphabet, and a tape
of length 𝑛𝑛?
a. 𝑘𝑘𝑎𝑎𝑛𝑛
b. 𝑘𝑘 + 𝑎𝑎 + 𝑛𝑛
c. 𝑘𝑘𝑎𝑎𝑛𝑛
d. 𝑘𝑘𝑛𝑛𝑎𝑎𝑛𝑛
3/24/2021 CS332 – Theory of Computation 13
LBA Halting
Theorem: Let 𝐵𝐵 be an LBA with 𝑘𝑘 states and 𝑎𝑎 symbols in
its tape alphabet. Then 𝐵𝐵 halts on input 𝑤𝑤 if and only if 𝐵𝐵
halts on input 𝑤𝑤 within 𝑘𝑘𝑛𝑛𝑎𝑎𝑛𝑛 steps.
Proof:
3/24/2021 CS332 – Theory of Computation 14
Deciding 𝐴𝐴LBA
𝐴𝐴LBA = { 𝐵𝐵,𝑤𝑤 ∣ 𝐵𝐵 is an LBA that accepts input 𝑤𝑤}
Theorem: 𝐴𝐴LBA is decidable
Proof: The following TM decides 𝐴𝐴LBA:
On input 〈𝐵𝐵,𝑤𝑤〉:
1. Simulate 𝐵𝐵 on input 𝑤𝑤 for 𝒌𝒌𝒌𝒌𝒂𝒂𝒌𝒌 steps
2. If simulation accepts, accept.
If simulation rejects or has not yet halted, reject.
3/24/2021 CS332 – Theory of Computation 15
LBAs can “check” TMs
LBAs are not powerful enough to perform general TM
computations themselves.
But they can check the computation of a general TM 𝑀𝑀 on
input 𝑤𝑤
𝐵𝐵 = “On input 𝑥𝑥 = 𝐶𝐶0,𝐶𝐶1, … ,𝐶𝐶ℓ a sequence of configs.:
Accept if all of the following hold, and reject otherwise:
1. 𝐶𝐶0 is the starting configuration of 𝑀𝑀 on 𝑤𝑤,
2. Every 𝐶𝐶𝑖𝑖+1 legally follows from 𝐶𝐶𝑖𝑖, and
3. 𝐶𝐶ℓ is an accepting configuration’’
What is the language of 𝐵𝐵?
3/24/2021 CS332 – Theory of Computation 16
Computation History Method
Reduction from the undecidable language 𝐴𝐴TM to a
language 𝐿𝐿 using the following idea:
Given an input 〈𝑀𝑀,𝑤𝑤〉 to 𝐴𝐴TM, the ability to solve 𝐿𝐿
enables checking the existence of an accepting
computation history for 𝑀𝑀 on 𝑤𝑤
Can be used to prove undecidability of 𝐸𝐸LBA, 𝐴𝐴𝐿𝐿𝐿𝐿CFG,
Post Correspondence Problem, first-order logic …
3/24/2021 CS332 – Theory of Computation 17
𝐸𝐸LBA is unrecognizable
𝐸𝐸LBA = { 𝐵𝐵 ∣ 𝐵𝐵 is an LBA recognizing ∅}
Theorem: 𝐴𝐴TM ≤m 𝐸𝐸LBA hence 𝐸𝐸LBA is unrecognizable
Proof: The following TM computes the reduction:
On input 𝑀𝑀,𝑤𝑤 :
1. Construct LBA 𝐵𝐵 as follows:
𝐵𝐵 = “On input 𝑥𝑥 = 𝐶𝐶0,𝐶𝐶1, … ,𝐶𝐶ℓ a sequence of configs.:
Accept if 𝑥𝑥 is an accepting computation history of
𝑀𝑀 on 𝑤𝑤. Otherwise, reject.
2. Output 𝐵𝐵 .
3/24/2021 CS332 – Theory of Computation 18
Recap of LBAs
LBAs are simple:
• Can determine whether an LBA halts on a given input by
checking if it repeats a configuration
• Implies 𝐴𝐴LBA is decidable
LBAs are powerful:
• An LBA can check the computation of a general TM on a
given input
• Implies 𝐸𝐸LBA is undecidable
3/24/2021 CS332 – Theory of Computation 19
Problems in Language Theory
3/24/2021 CS332 – Theory of Computation 20
𝑨𝑨𝐃𝐃𝐃𝐃𝐃𝐃
decidable
𝑨𝑨𝐋𝐋𝐋𝐋𝐃𝐃
decidable
𝑬𝑬𝐃𝐃𝐃𝐃𝐃𝐃
decidable
𝑬𝑬𝐋𝐋𝐋𝐋𝐃𝐃
undecidable
𝑬𝑬𝑬𝑬𝐃𝐃𝐃𝐃𝐃𝐃
decidable
𝑬𝑬𝑬𝑬𝐋𝐋𝐋𝐋𝐃𝐃
undecidable
𝑨𝑨𝐓𝐓𝐓𝐓
undecidable
𝑬𝑬𝐓𝐓𝐓𝐓
undecidable
𝑬𝑬𝑬𝑬𝐓𝐓𝐓𝐓
undecidable
Undecidable problems outside language theory
Post Correspondence Problem (PCP):
3/24/2021 CS332 – Theory of Computation 21
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
BU CS 332 – Theory of Computation
Mapping Reductions
Mapping Reductions: Implications
Example: Another reduction to 𝐸𝑄 TM
Example: Another reduction to 𝐸𝑄 TM
Consequences of 𝐴 TM ≤ m 𝐸𝑄 TM
𝐸𝑄 TM itself is also unrecognizable
Computation History Method
Problems in Language Theory
Linear Bounded Automata (LBA)
Configurations
Computing with Configurations
Counting Configurations
LBA Halting
Deciding 𝐴 LBA
LBAs can “check” TMs
Computation History Method
𝐸 LBA is unrecognizable
Recap of LBAs
Problems in Language Theory
Undecidable problems outside language theory