Theory of Computations,
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(π22, σ(0)), add(π41, π43))).
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, πki, and σ, we also allow this new function N(n) in our constructions? Let us call functions that can be obtained from 0, πki, σ, 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.