## Theory of Computations, Final Exam for the courseCS 5315, Spring 2013

Name: _____________________________________________________

1. Describe the function f = σ(PR(0, π31 + π32)) in normal terms. For this function f, what is the value f(6, 3)?

2. Prove, from scratch, that the remainder function % is primitive recursive and μ-recursive. Start with the definitions of a primitive recursive function and a μ-recursive function, and use only this definition in your proof -- do not use results that we proved in class.

3. Prove that not every μ-recursive function is primitive recursive.

4. Design a μ-recursive function f(a, b) that represent equality limited to truth values: f(0, 0) = f(1, 1) = 1, f(0, 1) = f(1, 0) = 0, and f(a, b) is undefined for all other pairs (a, b).

5. Prove that the union of two recursively enumerable sets A and B is recursively enumerable. Based on your proof, answer the following question: if a number 6 was generated by the algorithm corresponding to the second set at moment 3, when will this number be printed by an algorithm corresponding to the union?

6. To prove that the the union of two recursively enumerable sets A and B is recursively enumerable, a student proposed the following alternative algorithm: "First, we produce all the elements of A; then, we produce all the elements of B". Give an example when this algorithm will not work. Hint: sets can be infinite.

7. Prove that the halting set is recursively enumerable. If a program p = 1 halts on data d = 2 at moment t = 3, at what moment of time will the pair (p, d) printed by the corresponding algorithm?

8. Prove that the union of a decidable set and a recursively enumerable set is always recursively enumerable. Is such a union always decidable? If yes, prove it; if no, give a counter-example and explain why this is a counterexample.

9. Prove that it is not possible, given a program that always halts, to check whether this program always computes n4.

10. Design a Turing machine that computes a function f(n) = 2 * n in binary code (the number n is written starting with its highest bit; e.g., 610 = 1102 is written as # 1 1 0 # # ...) Use the general algorithm for generating a Turing machine for the composition to design a Turing machine that computes the function f(f(n)) = 4 * n.

11. 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. Which of these three classes contain the problem of computing the component-wise sum of two arrays (see Problem 14)? Ali-Baba problem? (Reminder: we have a list of objects with known prices pi and weights wi; we need to select some of these objects so that the total price is at least P and the total weight does not exceed W.)

12-13. Reduce the satisfiability problem for the formula (x1 \/ ~x2) & (~x1 \/ x2) & (x1 \/ x2 \/ ~x3) to:

• 3-coloring;
• 5-coloring;
• clique;
• Ali Baba problem (see Problem 11);
• interval computations.

14. Consider the problem of computing the component-wise sum c = (c1, ..., cn) of two vectors a = (a1, ..., an) and b = (b1, ..., bn), where ci = ai + bi

• 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.

15. If a probabilistic algorithm produces a result with the probability of error 1/2, how many times do we need to repeat it to reduce the probability of error to 2%?

16. Find what is Σ2PΠ4P.

17. Which class of the polynomial hierarchy corresponds to finding the value x at which a given objective function f(x) attains the smallest possible value?

18. What is the Kolmogorov complexity of a sequence 011011 ... 011 (repeated 2,013 times)?

19-20. Describe your project for the class. Describe someone else's project for the class.