**Name**

(Please do not forget to put your name on all extra sheets of paper)

1. *Primitive recursive functions -- a formalization of for-loops:*

- Translate, step-by-step, the following for-loop into a primitive
recursive
expression:
s = 0; for(int i = 1; i <= a; i++) for(int j = 1; j <= b; j++) {s += s;}

You can use the addition function add(a, b) in this expression. What is the value of this function when a = 2 and b = 3? - Translate, step-by-step, the following primitive recursive function
into a for-loop:

f = PR(π^{1}_{1}, σ(σ(π^{3}_{3}))); for this function f, what is the value f(2, 3)? Provide an explicit formula for the corresponding function. - Prove, from scratch, that the remainder function a % b 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.

2. *Beyond primitive recursive functions:*

- Is every computable function primitive recursive?
- if yes, prove it;
- if not, give a counter-example (just describe it, no need to prove that this is indeed a counter-example).

- Translate, step-by-step, the following while-loop into a mu-recursive
expression:
s = 0; while(s > a) {s += b;}

What is the value of this function when b = 2 and a = 3?

3. *Computable sets and functions:*

- Prove that the union of two recursively enumerable (r.e.) sets is always r.e.
- Prove that if a set A is r.e. and a set B is decidable, then their
union is always r.e.

Is this union always decidable?- if yes, prove it;
- if no, provide an example when the union is not decidable.

- Prove that it is not possible, given a program that always halts,
to check whether this program always computes n
^{2}+ 1.

4. *Turing machines:*

- design a Turing machine that computes f(n) = n + 1;
- design a Turing machine that computes g(n) = n − 1;
- use the general algorithm for composition to design a third Turing machine that computes the composition f(g(n)) of these two functions;
- trace this "composition" Turing machine on the example of the input n = 1.

5. *Feasible and not feasible: definitions*

- Define what is P, what is NP, what is NP-hard, and what is NP-complete; no need to give a detailed definition of reduction.
- For
each of these four classes, explain:
- whether this class contains the problem of adding n numbers, and
- whether this class contains the clique problem.

6. *Reductions from the NP-hardness proof*
Reduce the satisfiability problem for the formula

(x_{1} \/ ~x_{2}) & (~x_{1} \/
x_{3}) & (x_{1} \/ x_{2} \/
~x_{3}) to:

- 3-coloring;
- clique;
- subset sum problem;
- interval computations.

7. *Kolmogorov complexity:*

- What is Kolmogorov complexity? How is it related to randomness?
- What can we say about
the Kolmogorov complexity of a sequence 1010010001...
in which:
- we first have 1 zero between the two consecutive 1s,
- then, we have 2 zeros between the two consecutive 1s,
- then, we have 3 zeros between the two consecutive 1s,

8-9. *Parallelization and beyond:*
A straightforward algorithm takes time O(n) to compute the sum
of n numbers.

- Does this problem belong to the class NC? Explain your answer.
- Is NC a subset of P? equal to P? explain your answer.
- If we parallelize and take into account communication time, what is the fastest that we get with such parallel algorithms? Explain your answer.
- Where are similar arguments used in the proof that satisfiability is NP-hard?
- Explain what is the physics behind these arguments and how using non-Euclidean physics can potentially lead to faster computations -- such as solving NP-hard problems in polynomial time.

10. *Projects:*

- Briefly describe your project for this class, and explain how this project is related to theory of computation.
- Briefly describe someone else's project for this class, and explain how this project is related to theory of computation.