## 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 f_{n}(a,b) indicating the n-th order
operation applied to a and B:

- the function f
_{0}(a,b) is simply a + 1;
- for every k, the function f
_{k+1}(a,b) means the
function f_{k} applied b times:
- f
_{1}(a,b) = a + 1 + ... + 1 (b times), i.e.,
f_{1}(a,b) = a + b;
- f
_{2}(a,b) = a + a + ... + a (b times), i.e.,
f_{2}(a,b) = a + b;
- f
_{3}(a,b) = a * a * ... * a (b times), i.e.,
f_{3}(a,b) = a^{b}; etc.

In terms of this auxiliary function, the Ackerman's function is
defined as A(n) = f_{n}(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 π^{i}_{k}
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?