CS 5315, Final Exam, Wednesday, May 9, 2012


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

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

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

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

4. Is the intersection of two decidable sets decidable? If yes, prove; if no, give a counter-example and explain why this is a counterexample.

5. Is the intersection of two recursively enumerable sets recursively enumerable? If yes, prove; if no, give a counter-example and explain why this is a counterexample.

6-7. Design a Turing machine that computes a function f(n) = n + 1 in binary code. Assume that the number n is given starting from the smallest bit: for example, 810 = 10002 is given as # 0 0 0 1 # # # # ... The algorithm for adding 1 is simple: we replace all 1s by 0s until we meet the first 0 or blank space, after which we replace it with 1 and stop (do not forget to rewind the Turing machine). For example, for the above 8, there are no 1s after the initial blank, so we replace the first 0 by 1 and stop. For 1110 = 10112, which is represented as # 1 1 0 1, we should get # 0 0 1 1. Use the general algorithm for generating a Turing machine for the composition to design a Turing machine that computes the function f(f(n)) = f(n) + 1 = (n + 1) + 1 = n + 2.

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

9. What is the Kolmogorov complexity of a sequence 01000100 ... 0100 (repeated 5,092,012 times)?

10. 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 multiplying all numbers in a given array? the interval computations problem?

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

Use a greedy algorithm to find a solution to the original satisfiability problem.

12-13. A straightforward algorithm takes time O(n) to compute the product of all the elements in an array of size n.

14. 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%?

15. Find what is Π3PΠ2P.

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

17. Briefly describe your project for this class.

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