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 10 are to:
- Identify specific functions that cannot be computed by Turing Machines
- Develop skills for identifying uncomputable problems
- Build strategies for showing new problems to be uncomputable
- Undertand the definition of Universality in the context of Turing Machines
|Day||“Monday” Cohort||“Tuesday” Cohort||“Wednesday” Cohort||“Thursday” Cohort||“Friday” Cohort|
|Wed 27 Oct||Preparation||(week 9)||(week 9)||(week 9)||(week 9)|
|Thurs 28 Oct||Preparation||Preparation||(week 9)||(week 9)||(week 9)|
|Fri 29 Oct||Preparation||Preparation||Preparation||(week 9)||(week 9)|
|Sat 30 Oct||Prep Cohort Meeting||Preparation||Preparation||Preparation||(week 9)|
|Sun 31 Oct||Revision||Prep Cohort Meeting||Preparation||Preparation||Preparation|
|Mon 1 Nov||Assessed Meeting||Revision||Prep Cohort Meeting||Preparation||Preparation|
|Tues 2 Nov||Writeup Due||Assessed Meeting||Revision||Prep Cohort Meeting||Preparation|
|Wed 3 Nov||(week 11)||Writeup Due||Assessed Meeting||Revision||Prep Cohort Meeting|
|Thurs 4 Nov||(week 11)||(week 11)||Writeup Due||Assessed Meeting||Revision|
|Fri 5 Nov||(week 11)||(week 11)||(week 11)||Writeup Due||Assessed Meeting|
|Sat 6 Nov||(week 11)||(week 11)||(week 11)||(week 11)||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.
There is no programming portion for this week.
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.
You can play all the videos using this playlist, but don’t forget to take breaks: Week 10 Playlist (Note that in previous semesters the week in which this material was covered was labelled week 9).
This week’s content is most similar to that of these previous-semester’s cs3102 classes:
Self-Rejection (An Uncomputable Function) (17:13)
An Uncomputable Problem in Python (8:10)
Universal Turing Machines (8:54)
ACCEPTS, Practical but Uncomputable (15:53)
Computability in Theory vs Practice (8:50)