CS 5315, Final Exam, Tuesday, May 12, 2015

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(π11, σ(σ(π33))); 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 n2 + 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
(x1 \/ ~x2) & (~x1 \/ x3) & (x1 \/ x2 \/ ~x3) 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,
all the way to 1,000 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.