Week 12
Topics covered in class
- Arithmetic Hierarchy
- Hierarchy theorem
- Classification of unsolvable problems
- Tarski-Kuratowski algorithm
Relevant sections in the textbook
Chapter 8: sections 5-7. (Section 7 contains a few non-trivial examples.)
Recommended exercises from the book
Ch. 8.7: exercises 1, 2, 3.