Microsoft PowerPoint – CS332-Lec16-ann
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. is decidable is decidable
Negative uses: If reduces to and is undecidable,
then is also undecidable
Ex. is undecidable is decidable
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.
This is a reduction from to
3/17/2021 CS332 ‐ Theory of Computation 3
Equality Testing for TMs
What do we want out of the machines ?
a) iff b) iff
c) iff d) iff
On input :
1. Construct TMs , as follows:
= =
2. Run on input
3. If accepts, accept. Otherwise, reject.
This is a reduction from to
3/17/2021 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.
This is a reduction from to
3/17/2021 CS332 ‐ Theory of Computation 5
Regular 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
This is a reduction from to
3/17/2021 CS332 ‐ Theory of Computation 6
Regular 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:
= “On input ,
1. If 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 to
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
Prove that 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
∗ is undecidable
3/17/2021 CS332 ‐ Theory of Computation 33