Goals
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).
Schedule
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 
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:
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 writeup 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).
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 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 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.
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)