Goals
This week, we hope you’ll become experts at proving functions are uncomputable (and occasionally, computable). We introduce the “proof by reduction” technique, which is a tremendously useful way to prove properties about problems, and (as you will see in the Algorithms class) also to develop and analyze algorithmic solutions.
The main goals for Week 10 are to:
- Become comfortable with the terms decidable, recognizable, and computable, and how we talk about these properties for languages, functions, and problems.
- Learn how to do a proof by reduction, and to avoid the common pitfalls in constructing reduction proofs.
- Gain experience proving problems are computable and uncomputable (we use the terms uncomputable and noncomputable interchangably).
Schedule
The schedule this week is a webb of complexity because of Election Day, Tuesday 3 November, but we hope everyone will abide by these carefully devised changes. We will not hold any official course activities (assessed cohort meetings or scheduled office hours) on Election Day.
Please vote (and if you can, volunteer to be a poll worker)! (Note: if you are voting in Virginia, early voting is a great option, but ends on October 31.)
The schedule changes impact the “Tuesday” cohorts. Until now, the Tuesday cohorts have been the first to meet for a given week. This week, they will not meet on November 3, but will instead move to be the last cohorts to meet in Week 10 (and subsequent weeks) on November 10. The schedule lists Tuesday cohorts on “Break” from Wednesday 28 Oct through Wednesday 4 November (without the normal preparation Cohort Meeting that would be on 31 Oct/1 Nov). You can decide to meet if you would like then, of course, and use the opportunity to review past weeks or get an early start on Week 10, but that’s up to you. (If any other cohorts are thinking it is unfair that the Tuesday cohorts get this week break, recall that they had their first assessed cohort meetings on 1 September, only four days after the cohorts were arranged. We are, unfortunately, not able to provide a break week for the other cohorts since the semester ends on Tuesday, 24 November.)
For Thursday cohorts who have preparation meetings on Tuesdays, we hope you will arrange within your cohort a schedule that works for everyone. It is fine to move the preparation meeting to Monday or Wednesday if you can find a time that works for everyone, or to meet as normal on Tuesday if everyone has been able to vote early and does not have other election day commitments. If you aren’t able to find a solution that works for your cohort, please let us know.
| Day | "Tuesday" Cohort | "Wednesday" Cohort | "Thursday" Cohort | "Friday" Cohort | "Sunday" Cohort | "Monday" Cohort | |
|---|---|---|---|---|---|---|---|
| Wed 28 Oct | Break | (Week 9) | (Week 9) | (Week 9) | (Week 9) | (Week 9) | |
| Thu 29 Oct | Break | Preparation | (Week 9) | (Week 9) | (Week 9) | (Week 9) | |
| Fri 30 Oct | Break | Preparation | Preparation | (Week 9) | (Week 9) | (Week 9) | |
| Sat/Sun 31 Oct/1 Nov | Break | Preparation | Preparation | Preparation | (Week 9) | (Week 9) | |
| Mon 2 Nov | Break | Cohort Meeting | Preparation | Preparation | Preparation | (Week 9) | |
| Tue3 Nov | Election Day (no assessed cohort meetings or deadlines) | ||||||
| Wed 4 Nov | Preparation | Assessed Cohort Meeting | Preparation | Cohort Meeting | Preparation | Preparation | |
| Thu 5 Nov | Preparation | Write-up Due | Assessed Cohort Meeting | Preparation | Cohort Meeting | Preparation | |
| Fri 6 Nov | Preparation | Preparation | Write-up Due | Assessed Cohort Meeting | Preparation | Cohort Meeting | |
| Sat/Sun 7/8 Nov | Cohort Meeting | Week 11 | Week 11 | Write-up Due | Assessed Cohort Meeting | Preparation | |
| Mon 9 Nov | Preparation | Week 11 | Week 11 | Week 11 | Write-up Due | Assessed Cohort Meeting | |
| Tue 10 Nov | Assessed Cohort Meeting | Week 11 | Week 11 | Week 11 | Week 11 | Write-up Due | |
| Wed 11 Nov | Write-up Due | Week 11 | Week 11 | Week 11 | Week 11 | Week 11 | |
Cohort Problems
These are the problems you should discuss in your Cohort Meeting, and everyone in your cohort should be prepared to present and discuss solutions to at the Assessed Cohort Meeting:
Cohort Problems for Week 10 [PDF]
The problems are posted here and we think its a good idea to look at them early, but you’re not expected to be able to solve them until after doing the readings and watching the videos below.
After the Assessed Cohort Meeting, your Cohort Leader will select one problem that your cohort needs to write-up and submit. The write-up is due by 11:59pm on the day after your assessed cohort meeting (see the schedule above).
Problem Set 10 Template [zip].
Reading
Chapter 9: Universality and uncomputability [PDF]
You should have already read through the Section 9.3 (but reread any parts you are confused on), and read the new Sections 9.4 and 9.5 for this week.
Videos
You can play all the videos using this playlist, but don’t forget to take breaks: Week 10 Playlist
These videos are edited from these cs3102 classes (we don't generally recommend watching the unedited versions, but they are available if you want to):
-
(Fall 2019) Class 16: Reductions: Full Video, Slides
-
(Fall 2019) Class 17: Rice’s Theorem: Full Video, Slides. (Note that we do not include the first half or so of this class in the edited videos, which presents two more examples of uncomputability proofs by reduction. If you’d like to see more examples of these kinds of problems, please watch the full video for this class.)
-
(Fall 2019) Class 18: Review for Exam 2: Full Video, Slides. We include a few example problems from this exam review lecture, that we think will be helpful to you for the cohort problems this week.
Decidable, Recognizable, Computable (7:18)
An Undecidable Problem (8:10)
Proof by Reduction (17:54)
HALTS is Undecidable (7:19)
Finite is Undecidable (11:38)
Prints3 and IsMalware Are Undecidable (5:15)
Rice's Theorem (15:28)
The following three videos are problems from the exam review, so do not introduct new material, but provide more examples of how to prove functions are computable or uncomputable. You can find the problems they cover here: Fall 2019 Exam 2 Practice Problems, and are encouraged to try to solve them yourself before watching the videos. The Natural Numbers are Computable video is about Problem 9, and the Proving Uncomputability video is about Problem 14.
Proving Computability and Noncomputability (7:57)
The Natural Numbers are Computable (2:43)
Proving Uncomputability (Busy Boas and Busier Beavers) (8:55)