Computability & Complexity - Lecture 3

Topics:

Closure properties of the class of primitive recursive functions:

• definition by cases
• bounded sum and product
• bounded minimization
• iteration.

Primitive recursive sets:

• characteristic function
• bounded existential and universal quantification.