## 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:

• the function f0(a,b) is simply a + 1;
• for every k, the function fk+1(a,b) means the function fk applied b times:
• f1(a,b) = a + 1 + ... + 1 (b times), i.e., f1(a,b) = a + b;
• f2(a,b) = a + a + ... + a (b times), i.e., f2(a,b) = a + b;
• f3(a,b) = a * a * ... * a (b times), i.e., f3(a,b) = ab; etc.
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)

• What we do we gain, from practical viewpoint, when we prove that a problem is NP-hard?
• Why do we need to study Turing machines?