Week 5
Topics covered in class
- Universal functions, universal programs
- Proof that the universal function is computable
- Step predicates
- Proof that the step predicate is primitive recursive
- Normal form theorem; characterization of computable functions
- Definition of Recursively Enumerable sets
Relevant sections in the textbook
Chapter 4: section 3.
Recommended exercises from the book
Ch. 4.3: exercises 1,2,3,4.