Week 10

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

Schedule

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

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.

There is no programming portion for this week.

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

Introduction (3:20)

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)