Week 11

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 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).

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):

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)