Name

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₁₀ = 1000₂ 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₁₀ = 1011₂, 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 Π₃P^Π₂P.

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.