Automata,
Homeworks for the course
CS 5315, Spring 2016

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

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

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

2. (March 14) In the construction of the Ackerman's function, we use an auxiliary function fn(a,b) indicating the n-th order operation applied to a and B:

In terms of this auxiliary function, the Ackerman's function is defined as A(n) = fn(n,n).

Let us now define a different function B(n) = f(2n, 3n). By a B-primitive recursive function, we mean any function which is obtained from 0, σ, and πik by using composition and primitive recursion. Prove that there exists a computable function which is not B-primitive recursive.

3. (March 23)