Test 1 for the course

CS 5315, Spring 2016

Name: _____________________________________________________

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

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

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

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

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

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

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

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

3. Translate, step-by-step, the following primitive recursive function
into a for-loop: f =
σ(PR(multi(π^{2}_{1}, π^{2}_{2}),
mult(mult(π^{4}_{1}, π^{4}_{2}),
π^{4}_{3})).
For this function
f, what is the value f(2, 3, 1)? Provide an explicit formula for the
corresponding function.

4-5. Prove, from scratch, that remainder 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:

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

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

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

7. Translate-step-by-step, the following mu-recursive expression
into a while-loop:
f = μm.(m + a > b).
For this function f, what is
the value of f(2, 5)?

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 for your class project.