Class 14: Computability
TCS Chapter 6: Loops and Infinity
TCS Chapter 8: Universaility and Uncomputability
Alan M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem. 1936. (bug fix)
Problem Set 5
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.Class 13: Machines
TCS Chapter 6: Loops and Infinity
Class 12: Size Hierarchy
TCS Chapter 5: Code as data, data as code
Problem Set 4
Problem Set 4: Countess of Functions Problem Set 4 is available here: ps4.pdf (you will also need the ps4.zip file). It is due on Friday, 18 October at 4:19pm. This assignment involves both PDF and Jupyter parts, and you should submit both your ps4.ipynb and ps4.pdf files as attachments in collab. As far as we know, none of the problems are impossible (we may be wrong, of course, but none of them are intentionally impossible to solve).Class 11: Cost and Counting
TCS Chapter 5: Code as data, data as code
Exam 1 Comments
The comments on Exam 1 are here: PDF.
The original exam is here: PDF
Overall the class did very well on Exam 1. The average scores by problem are:
| Cover | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 15 | 9.8 | 9.3 | 9.8 | 9.5 | 6.7 | 8.7 | 8.8 | 8.9 | 7.9 |
Fall Break
Enjoy your Fall Break!
We will have no regularly scheduled office hours until after classes resume on October 9. We will return Exam 1 in class on Wednesday, October 9. There is no problem set due next week. Problem Set 4 will be due on Friday, 18 October.
Class 10: Exam Review
Exam 1 is in class Wednesday.
Please read the cover sheet before the exam: Exam 1 Cover Sheet
Problem Set 3
Comments
(PDF in collab).
Practice Problems Comments
Quantum supremacy using a programmable superconducting processor, Google AI Quantum and collaborators. Leaked preprint, August 2019.