Theory of Computations,
Test 1 for the course
CS 5315, Spring 2017

Name: _____________________________________________________

Up to 5 handwritten pages are allowed.

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 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 z = a * b;
for(int i = 1; i <= b; i++)
  {for (int j = 1; j <= c; j++)
     {z = z * a;}}

You can use 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(mult(π21, π22), mult(π41, π42, π44)).
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, πki, and σ, we also allow this auxiliary function f(n) in our constructions? Let us call functions that can be obtained from 0, πki, σ, 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.