CS 5315, Final Exam, Monday May 12, 2014


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

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 function a ≤ b is primitive recursive and μ-recursive. Start with the definitions of a primitive recursive and a μ-recursive functions, and use only these definitions in your proof -- do not use results that we proved in class as given, you must prove everything.

3. Is every primitive recursive function μ-recursive? Is every everywhere defined μ-recursive function primitive recursive? For each of these questions:

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

5. Is the difference A − B between two decidable sets decidable? If yes, prove it; if no, give a counter-example and explain why this is a counterexample.

6. Is the difference between two recursively enumerable sets recursively enumerable? If yes, prove it; if no, give a counter-example and explain why this is a counterexample.

7-8. Design a Turing machine that computes a function f(n) = 4 * n in binary code. Assume that the number n is given starting from the largest bit: for example, 810 = 10002 is given as # 1 0 0 0 # # # # ... The algorithm for multiplying by 4 is simple: we add 00 at the end. For example, for the above 8, we get # 1 0 0 0 0 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 * f(n) = 4 * (4 * n) = 16 * n.

9. A student produced a program, proved that this program always halts, and claims that this program always computes 4 * n. Is there a general way of checking whether this program always computes 4 * n? If yes, explain how, if no, prove that this is not possible.

10. What is the Kolmogorov complexity of a sequence 100100 ... 100 (repeated 2,014 times)?

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 four classes contain the problem of subtracting two matrices? the clique problem?

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

14-15. A straightforward sequential algorithm takes time O(n2) to compute the sum of two matrices.

16. 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 0.5%?

17. Find what is Σ2PΠ2P.

18. Which class of the polynomial hierarchy corresponds to minimization?

19. Briefly describe your project for this class.

20. Briefly describe someone else's project for this class.