PowerPoint Presentation
BU CS 332 – Theory of Computation
Lecture 15:
• Review mid-semester
feedback
• Reductions
Reading:
Sipser Ch 5.1
Mark Bun
March 15, 2021
What helps you learn best?
• Lectures in general (13)
• In-class examples / walkthroughs (11)
• Interaction in lecture, polls (7)
• Discussion sections in general (7)
• Gradescope check-ins (5)
• Homework – useful, appropriate length/difficulty (5)
• Automata Tutor, TM simulator (4)
• Office hours (4)
• Course organization, perspective (3)
• Annotated slides (3)
• Piazza use (3)
• Homework feedback
• Reading
3/15/2021 CS332 – Theory of Computation 2
What hinders your learning?
• Remote format, COVID / Zoom
fatigue (7)
• Course difficulty, recent
increase in difficulty (4)
• Proofs, proof assignments on
homework (2)
• Too theoretical / knowledge of
concepts but not how to use
them (2)
• Homework too long, too
difficult (2)
• Automata Tutor / Morphett
• Turing machines
• Starting homework late
• Vague answers in office hours
• Transferring lecture knowledge
to homework
• Delay on homework feedback
• Sipser book
• Difficulty finding collaborators
• Gradescope check-ins
• Instructor mistakes
• Weekly (vs. less frequent)
assignments
• Instructor handwriting
• Course pace too fast
• Can’t turn in late work
3/15/2021 CS332 – Theory of Computation 3
Suggestions for course improvement
• More office hours (3)
• More examples (3)
• Recommendations for what’s
expected on HW solutions (3)
• More polls, interaction (2)
• Better / more visible handwriting,
or type on slides (2)
• Faster turnaround on grades (2)
• +12 hours on HW submissions (2)
• Supplementary readings / videos
(2)
• Shorter breakouts in discussion
• Releasing homework earlier
• Guidance on how to prove things
• Homeworks build up from easier
to harder questions
• Homework solutions
• Tutoring sessions
• Old exam questions during
discussion
• More ungraded practice
• Less difficult homework
• Slower lectures
• Free A’s
3/15/2021 CS332 – Theory of Computation 4
Clarity of expectations
• Seems mostly clear
• Reminder of resources to take advantage of:
Sipser textbook
Lectures (slides, recordings, Gradescope check-ins)
Discussions (in-class meetings, solution recording, posted slides)
Homework feedback, posted solutions
Office hours
Piazza
• See Lecture 1, Slides 13-17 for more advice
3/15/2021 CS332 – Theory of Computation 5
Suggestions for self-improvement
• Keep up with readings (24)
“I believe reading the textbook is more helpful that students realize. I
have been reading the textbook inconsistently and I find the weeks
that I do the reading, I can better understand the lecture material.”
• Time management (10)
• Review lecture / discussion materials (8)
• Attend more office hours (5)
• Participate in class more actively (5)
• Attend more discussions (2)
• Do example problems in Sipser (2)
• Find collaborators
• Remember to do Gradescope check-ins
• Participate on Piazza
3/15/2021 CS332 – Theory of Computation 6
Discussion format / feedback
• Nadya’s awesome (9)
• Breakout rooms can be awkward / not useful (3)
• New format is more engaging, allow for solving more problems (2)
• Discussion problems too easy
3/15/2021 CS332 – Theory of Computation 7
Proposed Course Modifications
• Poll for more office hours, tutoring
• Discussions
– Keeping new format (class time for breakout rooms, solution
video after)
– Nadya will kick start discussion in quieter groups
• Homework more approachable and useful
– More explicit guidance on components of a complete solution
(See also lecture slides where I try to do this)
– Gradient from easier (mechanical) to harder (creative)
questions
3/15/2021 CS332 – Theory of Computation 8
Other questions / concerns
• Is the final cumulative?
Yes, with an emphasis on last third of material
• Is there a curve?
Can expect grade increases for scores especially in
the 50-75% range
• Specific concerns about test grades (especially relative
to HW)
Come talk to us about this. Office hours can be an
awkward time, so schedule an appointment
3/15/2021 CS332 – Theory of Computation 9
Undecidability and
Reductions
3/15/2021 CS332 – Theory of Computation 10
Undecidability / Unrecognizability
Definition: A language 𝐿𝐿 is undecidable if there is no TM
deciding 𝐿𝐿
Definition: A language 𝐿𝐿 is unrecognizable if there is no
TM recognizing 𝐿𝐿
3/15/2021 CS332 – Theory of Computation 11
Last time: Two explicit undecidable languages
𝑈𝑈𝑈𝑈 = 𝑀𝑀 𝑀𝑀 is a TM that does not accept on input 𝑀𝑀 }
• Shown directly by diagonalization
𝐴𝐴TM = 𝑀𝑀,𝑤𝑤 𝑀𝑀 is a TM that accepts input 𝑤𝑤}
• “Reduction” from the undecidability of 𝑈𝑈𝑈𝑈
3/15/2021 CS332 – Theory of Computation 12
Scientists vs. Engineers
A computer scientist and an engineer are stranded on a
desert island. They find two palm trees with one coconut
on each. The engineer climbs a tree, picks a coconut and
eats.
The computer scientist climbs the second tree, picks a
coconut, climbs down, climbs up the first tree and places
it there, declaring success.
“Now we’ve reduced the problem to one we’ve already
solved.” (Please laugh)
3/15/2021 CS332 – Theory of Computation 13
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/15/2021 CS332 – Theory of Computation 14
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 𝐵𝐵”
If 𝐴𝐴 reduces to 𝐵𝐵, and 𝐵𝐵 is decidable, what can we say
about 𝐴𝐴?
a) 𝐴𝐴 is decidable
b) 𝐴𝐴 is undecidable
c) 𝐴𝐴 might be either decidable or undecidable
3/15/2021 CS332 – Theory of Computation 15
Two uses of reductions
Positive uses: If 𝐴𝐴 reduces to 𝐵𝐵 and 𝐵𝐵 is decidable, then 𝐴𝐴
is also decidable
3/15/2021 CS332 – Theory of Computation 16
𝐸𝐸𝑄𝑄DFA = ⟨𝑈𝑈1,𝑈𝑈2⟩ 𝑈𝑈1,𝑈𝑈2 are DFAs and 𝐿𝐿(𝑈𝑈1) = 𝐿𝐿(𝑈𝑈2)}
Theorem: 𝐸𝐸𝑄𝑄DFA is decidable
Proof: The following TM decides 𝐸𝐸𝑄𝑄DFA
On input ⟨𝑈𝑈1,𝑈𝑈2⟩ , where 𝑈𝑈1,𝑈𝑈2 are DFAs:
1. Construct a DFA 𝑈𝑈 that recognizes the symmetric
difference 𝐿𝐿(𝑈𝑈1) △ 𝐿𝐿(𝑈𝑈2)
2. Run the decider for 𝐸𝐸DFA on 𝑈𝑈 and return its output
Two uses of reductions
Negative uses: If 𝐴𝐴 reduces to 𝐵𝐵 and 𝐴𝐴 is undecidable,
then 𝐵𝐵 is also undecidable
3/15/2021 CS332 – Theory of Computation 17
𝐴𝐴TM = 𝑀𝑀,𝑤𝑤 𝑀𝑀 is a TM that accepts input 𝑤𝑤}
Suppose 𝐻𝐻 decides 𝐴𝐴TM
Consider the following TM 𝑈𝑈.
On input 𝑀𝑀 where 𝑀𝑀 is a TM:
1. Run 𝐻𝐻 on input 𝑀𝑀, 𝑀𝑀
2. If 𝐻𝐻 accepts, reject. If 𝐻𝐻 rejects, accept.
Claim: 𝑈𝑈 decides
𝑈𝑈𝑈𝑈 = 𝑀𝑀 𝑀𝑀 is a TM that does not accept input 𝑀𝑀 }
Two uses of reductions
Negative uses: If 𝐴𝐴 reduces to 𝐵𝐵 and 𝐴𝐴 is undecidable,
then 𝐵𝐵 is also undecidable
Template for undecidability proof by reduction:
1. Suppose to the contrary that 𝐵𝐵 is decidable
2. Using a decider for 𝐵𝐵 as a subroutine, construct an
algorithm deciding 𝐴𝐴
3. But 𝐴𝐴 is undecidable. Contradiction!
3/15/2021 CS332 – Theory of Computation 18
Halting Problem
Computational problem: Given a program (TM) and input 𝑤𝑤,
does that program halt (either accept or reject) on input 𝑤𝑤?
Formulation as a language:
𝐻𝐻𝐴𝐴𝐿𝐿𝐻𝐻TM = 𝑀𝑀,𝑤𝑤 𝑀𝑀 is a TM that halts on input 𝑤𝑤}
Ex. 𝑀𝑀 = “On input 𝑥𝑥 (a natural number in binary):
For each 𝑦𝑦 = 1, 2, 3, … :
If 𝑦𝑦2 = 𝑥𝑥, accept. Else, continue.”
Is 𝑀𝑀, 101 ∈ 𝐻𝐻𝐴𝐴𝐿𝐿𝐻𝐻TM?
a) Yes, because 𝑀𝑀 accepts on input 101
b) Yes, because 𝑀𝑀 rejects on input 101
c) No, because 𝑀𝑀 rejects on input 101
d) No, because 𝑀𝑀 loops on input 101
3/15/2021 CS332 – Theory of Computation 19
Halting Problem
Computational problem: Given a program (TM) and input 𝑤𝑤,
does that program halt on input 𝑤𝑤?
Formulation as a language:
𝐻𝐻𝐴𝐴𝐿𝐿𝐻𝐻TM = 𝑀𝑀,𝑤𝑤 𝑀𝑀 is a TM that halts on input 𝑤𝑤}
Ex. 𝑀𝑀 = “On input 𝑥𝑥 (a natural number in binary):
For each 𝑦𝑦 = 1, 2, 3, … :
If 𝑦𝑦2 = 𝑥𝑥, accept. Else, continue.”
𝑀𝑀′ = “On input 𝑥𝑥 (a natural number in binary):
For each 𝑦𝑦 = 1, 2, 3, … , 𝑥𝑥 :
If 𝑦𝑦2 = 𝑥𝑥, accept. Else, continue.
Reject.”
3/15/2021 CS332 – Theory of Computation 20
Halting Problem
𝐻𝐻𝐴𝐴𝐿𝐿𝐻𝐻TM = 𝑀𝑀,𝑤𝑤 𝑀𝑀 is a TM that halts on input 𝑤𝑤}
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. Run 𝐻𝐻 on input 𝑀𝑀,𝑤𝑤
2. If 𝐻𝐻 rejects, reject
3. If 𝐻𝐻 accepts, run 𝑀𝑀 on 𝑤𝑤
4. If 𝑀𝑀 accepts, accept
Otherwise, reject.
This is a reduction from 𝐴𝐴TM to 𝐻𝐻𝐴𝐴𝐿𝐿𝐻𝐻TM
3/15/2021 CS332 – Theory of Computation 21
Halting Problem
Computational problem: Given a program (TM) and input
𝑤𝑤, does that program halt on input 𝑤𝑤?
• A central problem in formal verification
• Dealing with undecidability in practice:
– Use heuristics that are correct on most real instances,
but may be wrong or loop forever on others
– Restrict to a “non-Turing-complete” subclass of
programs for which halting is decidable
– Use a programming language that lets a programmer
specify hints (e.g., loop invariants) that can be
compiled into a formal proof of halting
3/15/2021 CS332 – Theory of Computation 22
Empty language testing for TMs
𝐸𝐸TM = 𝑀𝑀 𝑀𝑀 is a TM and 𝐿𝐿 𝑀𝑀 = ∅}
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. Run 𝑅𝑅 on input ???
This is a reduction from 𝐴𝐴TM to 𝐸𝐸TM
3/15/2021 CS332 – Theory of Computation 23
Empty language testing for TMs
𝐸𝐸TM = 𝑀𝑀 𝑀𝑀 is a TM and 𝐿𝐿 𝑀𝑀 = ∅}
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 𝑅𝑅 , accept. Otherwise, reject
This is a reduction from 𝐴𝐴TM to 𝐸𝐸TM
3/15/2021 CS332 – Theory of Computation 24
What do we want out of
machine 𝑁𝑁?
a) 𝐿𝐿(𝑁𝑁) is empty iff 𝑀𝑀
accepts 𝑤𝑤
b) 𝐿𝐿(𝑁𝑁) is non-empty iff 𝑀𝑀
accepts 𝑤𝑤
c) 𝐿𝐿(𝑀𝑀) is empty iff 𝑁𝑁
accepts 𝑤𝑤
d) 𝐿𝐿 𝑀𝑀 is non-empty iff 𝑁𝑁
accepts 𝑤𝑤
Empty language testing for TMs
𝐸𝐸TM = 𝑀𝑀 𝑀𝑀 is a TM and 𝐿𝐿 𝑀𝑀 = ∅}
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 𝑥𝑥:
Run 𝑀𝑀 on 𝑤𝑤 and output
the result.”
2. Run 𝑅𝑅 on input 𝑁𝑁
3. If 𝑅𝑅 rejects, accept. Otherwise, reject
This is a reduction from 𝐴𝐴TM to 𝐸𝐸TM
3/15/2021 CS332 – Theory of Computation 25
Interlude: Formalizing Reductions
(Sipser 6.3)
Informally: 𝐴𝐴 reduces to 𝐵𝐵 if a decider for 𝐵𝐵 can be used
to construct a decider for 𝐴𝐴
One way to formalize:
• An oracle for language 𝐵𝐵 is a device that can answer
questions “Is 𝑤𝑤 ∈ 𝐵𝐵?”
• An oracle TM 𝑀𝑀𝐵𝐵 is a TM that can query an oracle for 𝐵𝐵
in one computational step
𝐴𝐴 is Turing-reducible to 𝐵𝐵 (written 𝐴𝐴 ≤𝑇𝑇 𝐵𝐵) if there is an
oracle TM 𝑀𝑀𝐵𝐵 deciding 𝐴𝐴
3/15/2021 CS332 – Theory of Computation 26
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/15/2021 CS332 – Theory of Computation 27
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/15/2021 CS332 – Theory of Computation 28
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/15/2021 CS332 – Theory of Computation 29
BU CS 332 – Theory of Computation
What helps you learn best?
What hinders your learning?
Suggestions for course improvement
Clarity of expectations
Suggestions for self-improvement
Discussion format / feedback
Proposed Course Modifications
Other questions / concerns
Undecidability and Reductions
Undecidability / Unrecognizability
Last time: Two explicit undecidable languages
Scientists vs. Engineers
Reductions
Reductions
Two uses of reductions
Two uses of reductions
Two uses of reductions
Halting Problem
Halting Problem
Halting Problem
Halting Problem
Empty language testing for TMs
Empty language testing for TMs
Empty language testing for TMs
Interlude: Formalizing Reductions�(Sipser 6.3)
Equality Testing for TMs
Regular language testing for TMs
Regular language testing for TMs