Microsoft PowerPoint – CS332-Lec18-ann
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
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 and is decidable (resp. recognizable), then is
also decidable (resp. recognizable)
Corollary:
If and is undecidable (resp. unrecognizable),
then is also undecidable (resp. unrecognizable)
3/24/2021 CS332 ‐ Theory of Computation 3
Example: Another reduction to
3/24/2021 CS332 ‐ Theory of Computation 4
Theorem:
Proof: The following TM computes the reduction :
What should the inputs and outputs to be?
a) 𝑓 should take as input a pair 𝑀 ,𝑀 and output a pair 〈𝑀,𝑤〉
b) 𝑓 should take as input a pair 〈𝑀,𝑤〉 and output a pair 𝑀 ,𝑀
c) 𝑓 should take as input a pair 𝑀 ,𝑀 and either accept or reject
d) 𝑓 should take as input a pair 〈𝑀,𝑤〉 and either accept or reject
Example: Another reduction to
3/24/2021 CS332 ‐ Theory of Computation 5
Theorem:
Proof: The following TM computes the reduction :
On input :
1. Construct TMs , as follows:
= “On input 𝑥, = “On input 𝑥,
2. Output
Consequences of
1. Since is undecidable, is also undecidable
2. implies
Since is unrecognizable, is unrecognizable
3/24/2021 CS332 ‐ Theory of Computation 6
itself is also unrecognizable
3/24/2021 CS332 ‐ Theory of Computation 7
Theorem: 𝐴 hence is unrecognizable
Proof: The following TM computes the reduction:
On input :
1. Construct TMs , as follows:
= “On input 𝑥, = “On input 𝑥,
1. Ignore 𝑥 1. Ignore 𝑥 and reject”
2. Run 𝑀 on input 𝑤
3. If 𝑀 accepts, accept.
Otherwise, reject.”
2. Output
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. 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
Ex.
Computing with Configurations
A sequence of configurations ℓ is an accepting
computation history for TM (or LBA) on input if
1. is the start configuration
2. Every 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
Theorem: is decidable
Proof: The following TM decides :
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 𝑥 𝐶 ,𝐶 , … ,𝐶ℓ a sequence of configs.:
Accept if all of the following hold, and reject otherwise:
1. 𝐶 is the starting configuration of 𝑀 on 𝑤,
2. Every 𝐶 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 to a
language using the following idea:
Given an input to , the ability to solve
enables checking the existence of an accepting
computation history for on
Can be used to prove undecidability of ,
Post Correspondence Problem, first‐order logic …
3/24/2021 CS332 ‐ Theory of Computation 17
is unrecognizable
𝐸 𝐵 ∣ 𝐵 is an LBA recognizing ∅
Theorem: 𝐴 𝐸 hence 𝐸 is unrecognizable
Proof: The following TM computes the reduction:
On input 𝑀,𝑤 :
1. Construct LBA 𝐵 , as follows:
𝐵 , “On input 𝑥 𝐶 ,𝐶 , … ,𝐶ℓ 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 is decidable
LBAs are powerful:
• An LBA can check the computation of a general TM on a
given input
• Implies 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