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

Week 8

Goals

This week, we introduce the most important and widely used model of computation, the Turing machine, and start to address the big question of what can and cannot be computed by any machine with a finite description.

The main goals for Week 8 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 14 Oct Preparation (Week 7) (Week 7) (Week 7) (Week 7) (Week 7)
Thu 15 Oct Preparation Preparation (Week 7) (Week 7) (Week 7) (Week 7)
Fri 16 Oct Preparation Preparation Preparation (Week 7) (Week 7) (Week 7)
Sat/Sun 17/18 Oct Cohort Meeting Preparation Preparation Preparation (Week 7) (Week 7)
Mon 19 Oct Preparation Cohort Meeting Preparation Preparation Preparation (Week 7)
Tue 20 Oct Assessed Cohort Meeting Preparation Cohort Meeting Preparation Preparation Preparation
Wed 21 Oct Write-up Due Assessed Cohort Meeting Preparation Cohort Meeting Preparation Preparation
Thu 22 Oct Week 9 Write-up Due Assessed Cohort Meeting Preparation Cohort Meeting Preparation
Fri 23 Oct Week 9 Week 9 Write-up Due Assessed Cohort Meeting Preparation Cohort Meeting
Sat/Sun 24/25 Oct Week 9 Week 9 Week 9 Write-up Due Assessed Cohort Meeting Preparation
Mon 26 Oct Week 9 Week 9 Week 9 Week 9 Write-up Due Assessed Cohort Meeting
Tue 27 Oct Week 9 Week 9 Week 9 Week 9 Week 9 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 8 [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 8 Template [zip].

Reading

This week we discuss the material contained in Chapter 7: Loops and Infinity.

Turing Machines and other similar models of computing are taught in many different ways in many different places. In addition to the course materials, you’ll find plenty of other presentations of this material available on youtube, other textbooks, lecture slides from other universities, blog posts, etc. Please be advised that there are many subtly different presentations of Turing machines, and so what you see elsewhere may differ from what we covered, but the key ideas are universal and should be the same in any good presentation. Typically minor changes are made to the model either for convenience of the context, or so real-world running times are more similar to the running time of the model (more on this in future weeks).

Videos

You can play all the videos using this playlist, but don’t forget to take breaks: Week 8 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):

Warm-Up: Life on Mars (2:16)

Limitations of Finite Automata (6:40)

Breaktime

Turing Machines (5:37)

Turing Machine Examples (11:40)

Breaktime

What was Turing’s Model Modeling? (15:56)

Breaktime

Turing Machine Execution (9:13)

Breaktime

Turing Machine Variations (4:25)

Busy Beavers (5:12)

Breaktime

On Uncomputable Numbers (8:13)

Alan M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem. 1936. (bug fix)