**Name**

(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:

- if your answer is yes, prove it,
- if your answer is no, give a counterexample and explain why this is a counterexample.

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, 8_{10} =
1000_{2} 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
11_{10} = 1011_{2}, 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:

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

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

- How fast can we solve this problem -- if we ignore the communication time? Explain how exactly, and how many processors we need for such fast computations.
- Does this problem belong to the class NC? Explain your answer.
- Is NC equal 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 describe at least two different schemes for using non-standard physics can potentially lead to faster computations -- such as solving NP-hard problems in polynomial time.

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
Π_{3}P^{Π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.