Test 1 for the course

CS 5315, Spring 2015

Name: _____________________________________________________

1. Translate, step-by-step, the following for-loop into a primitive recursive expression:

int z = a * b; for (int j = 1; j <= d; j++) {z = z * z;}

You can use mult(., .) in this expression.

What is the value of this
function when a = 2, b = 1, and d = 2?

2. Translate, step-by-step, the following for-loop into a primitive recursive expression:

int z = a * b; for(int i = 1; i <= c; i++) {for (int j = 1; j <= d; j++) {z = z * z;}}

You can use mult(., .) in this expression.

What is the value of this
function when a = 1, b = 2, c = 2, and d = 2?

3. Translate, step-by-step, the following primitive recursive function into a for-loop:

4-5. Prove, from scratch, that division is primitive recursive. Start with the definitions of a primitive recursive function, and use only this definition in your proof -- do not simply mention results that we proved in class, prove them.

6. Translate, step-by-step, the following while-loop into a mu-recursive expression:

t = a; i = 1; while(t < b) {t = t * i; i++;}You can use mult(., .) and < in this expression.

What is the value of this function when a = 2 and b = 10?

7. Translate-step-by-step, the following mu-recursive expression into a while-loop:

8-9. In class, we proved
that not every computable function is primitive
recursive, by using Cantor's diagonal construction to define
an auxiliary function f(n) which is
computable but not primitive recursive. What if, in
addition to 0, π^{k}_{i}, and σ, we also
allow this auxiliary function f(n) in
our constructions? Let us call functions that can be obtained from
0, π^{k}_{i}, σ, and f by using composition and
primitive recursion *f-primitive
recursive* functions. Will then every computable function be
f-primitive recursive?

10. Briefly describe what you have done so far for your class project.