Week 4
Topics covered in class
- Ackermann functions: functions which are total and computable but not PR
- Coding of pairs, sequences
- Codings of programs
- Unsolvability of the Halting Problem
Relevant sections in the textbook
Chapter 3: section 8.
Chapter 4: sections 1,2.
Recommended exercises from the book
Ch. 3.8: exercises 1,3,4,5,6.
Ch. 4.1: exercises 1,2. Ch. 4.2. ex. 1,2,3,4.