Theory of Computations,
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 π21, a Turing machine that computes σ, and use the general algorithm for composition to design a third Turing machine that computes the composition. σ(π21). Trace your machine on the example of the input (1, 1). Hint: the result should be σ(π21(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.