Week 3
Topics covered in class
- Computable functions and predicates, macros
- Basic functions; composition of functions; primitive recursion
- PRC classes, primitive recursive functions
- Examples of PR functions
- PR predicates
- closure properties of PR functions/predicates: bounded sum and
products, bounded quantifiers, definition by cases.
Relevant sections in the textbook
Chapter 2: section 5. Chapter 3, sections 1-6.
Recommended Exercises.
Ch 2.5: ex. 3,4,5,10.
Ch 3.3: ex. 2,3.
Ch. 3.4: ex. 1, 2, 5, 9.
Ch. 3.6: Ex. 2, 3, 5,6.