Test 1 for the course

CS 5315, Spring 2020

Name: _____________________________________________________

Up to 5 handwritten pages are allowed.

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

int x = p + q; for (int i = 1; i <= r; i++) {x = x * q;}

You can use add(.,.) (sum) and
mult(., .) (product) in this expression.

What is the value of this
function when p = 1, q = 2, and r = 2?

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

int z = p + q; for(int i = 1; i <= r; i++) {for (int j = 1; j <= s; j++) {z = z * q;}}

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

What is the value of this
function when p = q = r = s = 2?

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

4-5. Prove, from scratch, that the function f(p, q) = p % (q / p)
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. Prove that the following function f(p, q) is
μ-recursive: f(p, q) = p % (q / p) when each of the values p and q
is either 1 or 2, and f(p, q) is undefined for other pairs (p, q).

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

8-9. Suppose that someone comes up with a new proof that not every
computable function is primitive recursive, by providing a new
example of a function N(n) which is computable but not primitive
recursive. What if, in addition to 0,
π^{k}_{i}, and σ, we also allow this new
function N(n) in our constructions? Let us call functions that can
be obtained from 0, π^{k}_{i}, σ, and
N(n) by using composition and primitive recursion *N-primitive
recursive* functions. Will then every computable function be
N-primitive recursive? Prove that your answer is correct.

10. Design Turing machines for computing n + 1 in unary and in binary
codes.