Goals
Last week, we used a counting argument to show that there must be some uncomputable functions (“some” here means infinitely many), but we didin’t find a specific uncomputable function. This week, we prove that a particular function is uncomputable, and explore the implications of finding an uncomputable function.
The main goals for Week 9 are to:
- Understand what cannot be computed by a finite automaton and why.
- Use and understand Turing Machines as a model of computing.
- Study a definition of computability.
- Explore the powers and limitations of Turing Machines.
- Understand why some numbers are uncomputable, and what this means.
- Learn different variations on Turing Machines and how they can be transformed.
Schedule
The schedule is identical to previous weeks, and repeated here (with updated dates).
| Day | "Tuesday" Cohort | "Wednesday" Cohort | "Thursday" Cohort | "Friday" Cohort | "Sunday" Cohort | "Monday" Cohort |
|---|---|---|---|---|---|---|
| Wed 21 Oct | Preparation | (Week 8) | (Week 8) | (Week 8) | (Week 8) | (Week 8) |
| Thu 22 Oct | Preparation | Preparation | (Week 8) | (Week 8) | (Week 8) | (Week 8) |
| Fri 23 Oct | Preparation | Preparation | Preparation | (Week 8) | (Week 8) | (Week 8) |
| Sat/Sun 24/25 Oct | Cohort Meeting | Preparation | Preparation | Preparation | (Week 8) | (Week 8) |
| Mon 26 Oct | Preparation | Cohort Meeting | Preparation | Preparation | Preparation | (Week 8) |
| Tue 27 Oct | Assessed Cohort Meeting | Preparation | Cohort Meeting | Preparation | Preparation | Preparation |
| Wed 28 Oct | Write-up Due | Assessed Cohort Meeting | Preparation | Cohort Meeting | Preparation | Preparation |
| Thu 29 Oct | Week 10 | Write-up Due | Assessed Cohort Meeting | Preparation | Cohort Meeting | Preparation |
| Fri 30 Oct | Week 10 | Week 10 | Write-up Due | Assessed Cohort Meeting | Preparation | Cohort Meeting |
| Sat/Sun 31 Oct/1 Nov | Week 10 | Week 10 | Week 10 | Write-up Due | Assessed Cohort Meeting | Preparation |
| Mon 2 Nov | Week 10 | Week 10 | Week 10 | Week 10 | Write-up Due | Assessed Cohort Meeting |
| Tue 3 Nov | Election Day (no assessed cohort meetings or deadlines) | |||||
| Wed 4 Nov | Week 10 | Week 10 | Week 10 | Week 10 | Week 10 | Write-up 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:
Cohort Problems for Week 9 [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).
Reading
Chapter 9: Universality and uncomputability [PDF]
You should read through the end of Section 9.3 (including the “optional” section 9.3.2). (We will cover Section 9.4 and 9.5 next week.)
The material in Sections 9.1 – 9.3 covers the same concepts as we do in the lectures, but in a somewhat different order and with a focus on HALT rather than ACCEPTS. You should consider how similar and different these two functions are, and compare the proof that ACCEPTS is uncomputable from the lectures to the one in the book that HALT is uncomputable.
Videos
You can play all the videos using this playlist, but don’t forget to take breaks: Week 9 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 14: Computability: Full Video, Slides (just part of the Self-Rejection (An Uncomputable Function) video)
-
(Fall 2019) Class 15: Universality and Uncomputability: Full Video, Slides
Church-Turing Thesis (8:39)
Self-Rejection (An Uncomputable Function) (16:30)
Universal Machines (8:54)
ACCEPTS is Uncomputable (Part 1) (6:12)
ACCEPTS is Uncomputable (Part 2) (6:23)
Computability in Theory and Practice (8:50)
This video was originally planned for Week 10 and is a recap of the proof that acceptance is uncomputable. But, since it will be helpful for one of the cohort problems this week, we are providing it here.
An Undecidable Problem (8:10)
Alan M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem. 1936. (bug fix) (You missed your chance to by an original printing for GBP 30,000.)
According to Scott Aaronson, Dori-Mic and the Universal Machine! A Tragicomic Tale of Combinatorics and Computability for Curious Children of All Ages is “The BEST babies’ book about computational universality I’ve read.". I have free copies to send to anyone who needs a holiday present for a young sibling/cousin/nibling/other person who is behind in her theoretical computer science education and needs a holiday present for any cs3102 students who ask (this offer doesn’t expire).