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

Problem Set 6

26 October 2019 by David Evans and Nathan Brunelle

Problem Set 6: Dodge Duck Dip Dive Decide

Problem Set 6 is available here: ps6.pdf (you will also need the ps6.zip file). It is due on Friday, 1 November at 4:19pm.

These is no Jupyter part for PS6, so your submission can be just one ps6.pdf file.

This assignment covers Turing Machines from Chapter 6, and undecidability (including the halting problem, reductions, and Rice’s theorem) from Chapter 8.