This is an archived page from the Fall 2019 version of the course.
For the latest version, see https://uvatoc.github.io.

Week 10

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

Decidable, Recognizable, Computable (7:18)

An Undecidable Problem (8:10)

Breaktime

Proof by Reduction (17:54)

Breaktime

HALTS is Undecidable (7:19)

Finite is Undecidable (11:38)

Prints3 and IsMalware Are Undecidable (5:15)

Breaktime

Rice's Theorem (15:28)

Breaktime

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)

Breaktime