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

Problem Set 5

19 October 2019 by David Evans and Nathan Brunelle

Problem Set 5: Loopy Tunes

Problem Set 5 is available here: ps5.pdf (you will also need the ps5.zip file). It is due on Friday, 25 October at 4:19pm.

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

This assignment covers the Size Hierarchy from Chapter 5, Finite State Macines from Class 12 and Class 13, and Turing Machines, NAND-TM, and computability from Chapter 5, Class 13 and Class 14.