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

Week 9

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

Problem Set 9 Template [zip].

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

Church-Turing Thesis (8:39)

Breaktime

Self-Rejection (An Uncomputable Function) (16:30)

Breaktime

Universal Machines (8:54)

Breaktime

ACCEPTS is Uncomputable (Part 1) (6:12)

ACCEPTS is Uncomputable (Part 2) (6:23)

Breaktime

Computability in Theory and Practice (8:50)

Breaktime

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