Theory of Computations,
Quiz 1 for the course
CS 5315, Spring 2012

Name ___________________________________________________

Books and notes allowed.

1. What is a primitive recursive function? Explain what primitive recursion is.

2. What is a mu-recursive function? Explain what mu-recursion is.

3. Describe μm.P(m) as a while-loop.

4. Describe a general primitive recursion as a for-loop.