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

Name: _____________________________________________________

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

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

You can use mult(., .) in this expression.
What is the value of this function when a = 2, b = 1, and d = 2?

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

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

You can use mult(., .) in this expression.
What is the value of this function when a = 1, b = 2, c = 2, and d = 2?

3. Translate, step-by-step, the following primitive recursive function into a for-loop:

f = σ(PR(sum(π21, π21), sum(sum(π42, π43), π44)).
For this function f, what is the value f(2, 3, 4)? Provide an explicit formula for the corresponding function.

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

t = a; i = 1;
while(t < b)
  {t = t * i; i++;}
You can use mult(., .) and < in this expression.
What is the value of this function when a = 2 and b = 10?

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, π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?

10. Briefly describe what you have done so far for your class project.