Test 1 for the course

CS 5315, Spring 2018

Name: _____________________________________________________

Up to 5 handwritten pages are allowed.

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

int x = a + b; for (int i = 1; i <= a; i++) {x = x * b;}

You can use add(.,.) (sum) and
mult(., .) (product) 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 x = a + b; for(int i = 1; i <= a; i++) {for (int j = 1; j <= c; j++) {x = x * b;}}

You can use add(.,.) amd mult(., .) 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(add(π^{2}_{1}, π^{2}_{2}),
add(π^{4}_{1}, π^{4}_{3},
π^{4}_{4})).
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 integer division a / b
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(a, b) is
μ-recursive: f(a, b) = a || (!b) when a and b are both equal to
either 0 or 1, and f(a, b) is undefined for other pairs (a, b).

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, 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? Prove that your answer is correct.