This week, we hope you’ll become comfortable 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 11 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).
|Day||“Monday” Cohort||“Tuesday” Cohort||“Wednesday” Cohort||“Thursday” Cohort||“Friday” Cohort|
|Wed 03 Nov||Preparation||(Week 10)||(Week 10)||(Week 10)||(Week 10)|
|Thurs 04 Nov||Preparation||Preparation||(Week 10)||(Week 10)||(Week 10)|
|Fri 05 Nov||Preparation||Preparation||Preparation||(Week 10)||(Week 10)|
|Sat 06 Nov||Prep Cohort Meeting||Preparation||Preparation||Preparation||(Week 10)|
|Sun 07 Nov||Revision||Prep Cohort Meeting||Preparation||Preparation||Preparation|
|Mon 08 Nov||Assessed Meeting||Revision||Prep Cohort Meeting||Preparation||Preparation|
|Tues 09 Nov||Writeup Due||Assessed Meeting||Revision||Prep Cohort Meeting||Preparation|
|Wed 10 Nov||(Week 12)||Writeup Due||Assessed Meeting||Revision||Prep Cohort Meeting|
|Thurs 11 Nov||(Week 12)||(Week 12)||Writeup Due||Assessed Meeting||Revision|
|Fri 12 Nov||(Week 12)||(Week 12)||(Week 12)||Writeup Due||Assessed Meeting|
|Sat 13 Nov||(Week 12)||(Week 12)||(Week 12)||(Week 12)||Writeup Due|
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:
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.
Similarly to Week 5, for this week you will be assigned a new problem to solve for your write-up problem which you will need to solve on your own without any collaboration. This will be due 48 hours after your cohort meeting (instead of the usual 24 hours). This problem will expect you to do a reduction proof, similar to the ones in the cohort problems (but different enough to be new).
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.
You can play all the videos using this playlist, but don’t forget to take breaks: Week 11 Playlist (note that in past weeks this unit was labelled as Week 10)
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 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.)
Week 10 Intro (3:58)
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 introduce 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)