Test 2 for the course

CS 5315, Spring 2015

Name: _____________________________________________________

1. Prove that the intersection of two recursively enumerable (r.e.) sets is always r.e.

2. Prove that if a set A is r.e. and a set B is decidable, then their intersection is always r.e. Is this intersection always decidable? If yes, prove it; if no, provide an example when the intersection is not decidable.

3. Prove that it is not possible, given a program that always halts, to check whether this program always computes σ(n) = n + 1.

4-5. Design a Turing machine that computes a projection
function π^{2}_{1}, a Turing machine that computes
σ, and use the general algorithm for composition to
design a third Turing machine that computes the composition.
σ(π^{2}_{1}). Trace your machine on the
example of the input (1, 1). *Hint:* the result should be
σ(π^{2}_{1}(1, 1)) = σ(1) = 2.

6. Translate, step-by-step, the following for-loop into a primitive recursive expression:

s = 0; for(int i = 1; i <= a; i++) {s -= b;}You can use substraction minus(a, b) in this expression. What is the value of this function when b = 2 and a = 3?

7. Translate, step-by-step, the following while-loop into a mu-recursive expression:

s = 0; while(s > a) {s -= b;}What is the value of this function when b = 2 and a = −3?

8. What is the Kolmogorov complexity of a sequence 1010 ... 10 (repeated 2015 times)?

9. Use a general algorithm to transform the following propositional formula into CNF form: a > b.

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. For each of these four classes, explain whether this class contains the problem of sorting a given list, and whether this class contains the propositional satisfiability problem.