PowerPoint Presentation
BU CS 332 – Theory of Computation
Lecture 16:
• Examples of Reductions
• Test 2 Review
Reading:
Sipser Ch 5.1
Mark Bun
March 15, 2021
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/17/2021 CS332 – Theory of Computation 2
Positive uses: If 𝐴𝐴 reduces to 𝐵𝐵 and 𝐵𝐵 is decidable, then 𝐴𝐴
is also decidable
Ex. 𝐸𝐸DFA is decidable ⇒ 𝐸𝐸𝐸𝐸DFA is decidable
Negative uses: If 𝐴𝐴 reduces to 𝐵𝐵 and 𝐴𝐴 is undecidable,
then 𝐵𝐵 is also undecidable
Ex. 𝐴𝐴TM is undecidable ⇒𝐻𝐻𝐴𝐴𝐻𝐻𝐻𝐻TM is decidable
Equality Testing for TMs
𝐸𝐸𝐸𝐸TM = 𝑀𝑀1,𝑀𝑀2 𝑀𝑀1,𝑀𝑀2 are TMs and 𝐻𝐻 𝑀𝑀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:
On input 𝑀𝑀 :
1. Construct TMs 𝑁𝑁1, 𝑁𝑁2 as follows:
𝑁𝑁1 = 𝑁𝑁2 =
2. Run 𝑅𝑅 on input 𝑁𝑁1,𝑁𝑁2
3. If 𝑅𝑅 accepts, accept. Otherwise, reject.
This is a reduction from 𝐸𝐸TM to 𝐸𝐸𝐸𝐸TM
3/17/2021 CS332 – Theory of Computation 3
Equality Testing for TMs
What do we want out of the machines 𝑁𝑁1,𝑁𝑁2?
a) 𝐻𝐻 𝑀𝑀 = ∅ iff 𝑁𝑁1 = 𝑁𝑁2 b) 𝐻𝐻 𝑀𝑀 = ∅ iff 𝐻𝐻 𝑁𝑁1 = 𝐻𝐻 𝑁𝑁2
c) 𝐻𝐻 𝑀𝑀 = ∅ iff 𝑁𝑁1 ≠ 𝑁𝑁2 d) 𝐻𝐻 𝑀𝑀 = ∅ iff 𝐻𝐻 𝑁𝑁1 ≠ 𝐻𝐻 𝑁𝑁2
On input 𝑀𝑀 :
1. Construct TMs 𝑁𝑁1, 𝑁𝑁2 as follows:
𝑁𝑁1 = 𝑁𝑁2 =
2. Run 𝑅𝑅 on input 𝑁𝑁1,𝑁𝑁2
3. If 𝑅𝑅 accepts, accept. Otherwise, reject.
This is a reduction from 𝐸𝐸TM to 𝐸𝐸𝐸𝐸TM
3/17/2021 CS332 – Theory of Computation 4
Equality Testing for TMs
𝐸𝐸𝐸𝐸TM = 𝑀𝑀1,𝑀𝑀2 𝑀𝑀1,𝑀𝑀2 are TMs and 𝐻𝐻 𝑀𝑀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:
On input 𝑀𝑀 :
1. Construct TMs 𝑁𝑁1, 𝑁𝑁2 as follows:
𝑁𝑁1 = 𝑁𝑁2 =
2. Run 𝑅𝑅 on input 𝑁𝑁1,𝑁𝑁2
3. If 𝑅𝑅 accepts, accept. Otherwise, reject.
This is a reduction from 𝐸𝐸TM to 𝐸𝐸𝐸𝐸TM
3/17/2021 CS332 – Theory of Computation 5
Regular language testing for TMs
𝑅𝑅𝐸𝐸𝑅𝑅TM = 𝑀𝑀 𝑀𝑀 is a TM and 𝐻𝐻 𝑀𝑀 is regular}
Theorem: 𝑅𝑅𝐸𝐸𝑅𝑅TM is undecidable
Proof: Suppose for contradiction that there exists a decider 𝑅𝑅
for 𝑅𝑅𝐸𝐸𝑅𝑅TM. We construct a decider for 𝐴𝐴TM as follows:
On input 𝑀𝑀,𝑤𝑤 :
1. Construct a TM 𝑁𝑁 as follows:
2. Run 𝑅𝑅 on input 𝑁𝑁
3. If 𝑅𝑅 accepts, accept. Otherwise, reject
This is a reduction from 𝐴𝐴TM to 𝑅𝑅𝐸𝐸𝑅𝑅TM
3/17/2021 CS332 – Theory of Computation 6
Regular language testing for TMs
𝑅𝑅𝐸𝐸𝑅𝑅TM = 𝑀𝑀 𝑀𝑀 is a TM and 𝐻𝐻 𝑀𝑀 is regular}
Theorem: 𝑅𝑅𝐸𝐸𝑅𝑅TM is undecidable
Proof: Suppose for contradiction that there exists a decider 𝑅𝑅
for 𝑅𝑅𝐸𝐸𝑅𝑅TM. We construct a decider for 𝐴𝐴TM as follows:
On input 𝑀𝑀,𝑤𝑤 :
1. Construct a TM 𝑁𝑁 as follows:
𝑁𝑁 = “On input 𝑥𝑥,
1. If 𝑥𝑥 ∈ 0𝑛𝑛1𝑛𝑛 𝑛𝑛 ≥ 0}, accept
2. Run TM 𝑀𝑀 on input 𝑤𝑤
3. If 𝑀𝑀 accepts, accept. Otherwise, reject.”
2. Run 𝑅𝑅 on input 𝑁𝑁
3. If 𝑅𝑅 accepts, accept. Otherwise, reject
This is a reduction from 𝐴𝐴TM to 𝑅𝑅𝐸𝐸𝑅𝑅TM
3/17/2021 CS332 – Theory of Computation 7
Test 2 Topics
3/17/2021 CS332 – Theory of Computation 8
Turing Machines (3.1, 3.3)
• Know the three different “levels of abstraction” for
defining Turing machines and how to convert between
them: Formal/state diagram, implementation-level, and
high-level
• Know the definition of a configuration of a TM and the
formal definition of how a TM computes
• Know how to “program” Turing machines by giving state
diagrams and implementation-level descriptions
• Understand the Church-Turing Thesis
3/17/2021 CS332 – Theory of Computation 9
TM Variants (3.2)
• Understand the following TM variants: TM with stay-put,
TM with two-way infinite tape, Multi-tape TMs,
Nondeterministic TMs
• Know how to give a simulation argument
(implementation-level and high-level description) to
compare the power of TM variants
• Understand the specific simulation arguments we’ve
seen: two-way infinite TM by basic TM, multi-tape TM
by basic TM, nondeterministic TM by basic TM
3/17/2021 CS332 – Theory of Computation 10
Decidability (4.1)
• Understand how to use a TM to simulate another
machine (DFA, another TM)
• Know the specific decidable languages from language
theory that we’ve discussed, and how to decide them:
𝐴𝐴𝐷𝐷𝐷𝐷𝐷𝐷, 𝐸𝐸𝐷𝐷𝐷𝐷𝐷𝐷,𝐸𝐸𝐸𝐸𝐷𝐷𝐷𝐷𝐷𝐷, etc.
• Know how to use a reduction to one of these languages
to show that a new language is decidable
3/17/2021 CS332 – Theory of Computation 11
Undecidability (4.2)
• Know the definitions of countable and uncountable sets
and how to prove countability and uncountability
• Understand how diagonalization is used to prove the
existence of an explicit undecidable language 𝑈𝑈𝑈𝑈
• Know that a language is decidable iff it is recognizable
and its complement is recognizable, and understand the
proof
3/17/2021 CS332 – Theory of Computation 12
Reducibility (5.1)
• Understand how to use a reduction (contradiction
argument) to prove that a language is undecidable
• Know the reductions showing that 𝐻𝐻𝐴𝐴𝐻𝐻𝐻𝐻𝑇𝑇𝑇𝑇,
𝐸𝐸𝑇𝑇𝑇𝑇,𝑅𝑅𝐸𝐸𝑅𝑅𝑈𝑈𝐻𝐻𝐴𝐴𝑅𝑅𝑇𝑇𝑇𝑇,𝐸𝐸𝐸𝐸𝑇𝑇𝑇𝑇 are undecidable
• You are not responsible for understanding the
computation history method.
3/17/2021 CS332 – Theory of Computation 13
True or False
3/17/2021 CS332 – Theory of Computation 14
• It’s all about the justification!
• The logic of the argument has to be clear
• Restating the question is not justification; we’re
looking for additional insight
Simulation arguments, constructing deciders
3/17/2021 CS332 – Theory of Computation 15
• Full credit for a clear and correct description of the new machine
• Can still be a good idea to provide an explanation
(partial credit, clarifying ambiguity)
Countability proofs
3/17/2021 CS332 – Theory of Computation 16
• Describe how to list all the elements in your set, usually
in a succession of finite “stages”
• Describe how this listing process gives you a bijection
from the natural numbers
Uncountability proofs
3/17/2021 CS332 – Theory of Computation 17
• The 2-D table is useful for helping you think about
diagonalization, but does not need to appear in the proof
• The essential part of the proof is the construction of the
“inverted diagonal” element, and the proof that it works
Undecidability proofs
3/17/2021 CS332 – Theory of Computation 18
Practice Problems
3/17/2021 CS332 – Theory of Computation 19
3/17/2021 CS332 – Theory of Computation 20
3/17/2021 CS332 – Theory of Computation 21
3/17/2021 CS332 – Theory of Computation 22
3/17/2021 CS332 – Theory of Computation 23
Decidability and
Recognizability
3/17/2021 CS332 – Theory of Computation 24
Let
Show that 𝐴𝐴 is decidable
3/17/2021 CS332 – Theory of Computation 25
𝐴𝐴 = { 𝑈𝑈 |
𝑈𝑈 is a DFA that does not accept any string
containing an odd number of 1′s}
Prove that 𝐸𝐸TM is recognizable
3/17/2021 CS332 – Theory of Computation 26
Prove that if 𝐴𝐴 and 𝐵𝐵 are decidable, then so is
𝐴𝐴 \ 𝐵𝐵
3/17/2021 CS332 – Theory of Computation 27
Countable and
Uncountable Sets
3/17/2021 CS332 – Theory of Computation 28
Show that the set of all valid (i.e., compiling
without errors) C++ programs is countable
3/17/2021 CS332 – Theory of Computation 29
A Celebrity Twitter Feed is an infinite sequence of ASCII
strings, each with at most 140 characters. Show that the set
of Celebrity Twitter Feeds is uncountable.
3/17/2021 CS332 – Theory of Computation 30
Undecidability and
Unrecognizability
3/17/2021 CS332 – Theory of Computation 31
Prove or disprove: If 𝐴𝐴 and 𝐵𝐵 are
recognizable, then so is 𝐴𝐴 \ 𝐵𝐵
3/17/2021 CS332 – Theory of Computation 32
Prove that the language 𝐴𝐴𝐻𝐻𝐻𝐻TM =
{ 𝑀𝑀 |𝑀𝑀 is a TM and 𝐻𝐻 𝑀𝑀 = Σ∗} is undecidable
3/17/2021 CS332 – Theory of Computation 33
BU CS 332 – Theory of Computation
Reductions
Equality Testing for TMs
Equality Testing for TMs
Equality Testing for TMs
Regular language testing for TMs
Regular language testing for TMs
Test 2 Topics
Turing Machines (3.1, 3.3)
TM Variants (3.2)
Decidability (4.1)
Undecidability (4.2)
Reducibility (5.1)
True or False
Simulation arguments, constructing deciders
Countability proofs
Uncountability proofs
Undecidability proofs
Practice Problems
Slide Number 20
Slide Number 21
Slide Number 22
Slide Number 23
Decidability and Recognizability
Let���Show that 𝐴 is decidable
Prove that 𝐸 TM is recognizable
Prove that if 𝐴 and 𝐵 are decidable, then so is 𝐴 \ 𝐵
Countable and �Uncountable Sets
Show that the set of all valid (i.e., compiling without errors) C++ programs is countable
A Celebrity Twitter Feed is an infinite sequence of ASCII strings, each with at most 140 characters. Show that the set of Celebrity Twitter Feeds is uncountable.
Undecidability and Unrecognizability
Prove or disprove: If 𝐴 and 𝐵 are recognizable, then so is 𝐴 \ 𝐵
Prove that the language 𝐴𝐿𝐿 TM ={ 𝑀 |𝑀 is a TM and 𝐿 𝑀 = Σ ∗ } is undecidable