Microsoft PowerPoint – CS332-Lec15-ann
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
• Shown directly by diagonalization
• “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
Theorem: is decidable
Proof: The following TM decides
On input , where are DFAs:
1. Construct a DFA that recognizes the symmetric
difference
2. Run the decider for 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
𝐴 𝑀,𝑤 𝑀 is a TM that accepts input 𝑤
Suppose 𝐻 decides 𝐴
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:
Ex. = “On input (a natural number in binary):
For each :
If , accept. Else, continue.”
Is
a) Yes, because accepts on input
b) Yes, because rejects on input
c) No, because rejects on input
d) No, because loops on input
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:
Ex. = “On input (a natural number in binary):
For each :
If , accept. Else, continue.”
= “On input (a natural number in binary):
For each :
If , accept. Else, continue.
Reject.”
3/15/2021 CS332 ‐ Theory of Computation 20
Halting Problem
Theorem: is undecidable
Proof: Suppose for contradiction that there exists a decider
for . We construct a decider for 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 to
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
Theorem: is undecidable
Proof: Suppose for contradiction that there exists a decider
for . We construct a decider for as follows:
On input :
1. Run on input ???
This is a reduction from to
3/15/2021 CS332 ‐ Theory of Computation 23
Empty 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 , accept. Otherwise, reject
This is a reduction from to
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
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
Run on and output
the result.”
2. Run on input
3. If rejects, accept. Otherwise, reject
This is a reduction from to
3/15/2021 CS332 ‐ Theory of Computation 25