## Theory of Computation, Homeworks for the course CS 5315, Spring 2015

1. (Due February 3) Translate, step-by-step, the following for-loop into a primitive recursive expression:

```int z = a + b;
for(int i = 1; i <= c; i++)
{z = z + a * b;}
```

2. (Due February 3) Translate, step-by-step, the following primitive recursive expression into a for-loop: PR(mult(π21, π22), σ(π44)). Provide an explicit formula for the corresponding function.

3. (Due February 10) Prove that if P(n), Q(n), f(n), g(n), and h(n) are primitive recursive, then the function

if P(n) then f(n) elseif Q(n) then g(n) else h(n)
is also primitive recursive.

4. (Due February 10) Submit a 1-page report on the progress you made on your project during the work-on-your-project day (February 5).

5. (Due February 12) Write down a proof that there exists a computable function which is not primitive recursive. This must be a detailed text, with all the words and all needed formulas, so that a reader who is not familiar with this result will understand and be convinced that this is true. By February 12, it is Ok to have a proof with gaps clearly indicating that some parts are still not clear; a full proof with all details right is expected by February 17.

6. (Due February 19) Let us call a function Ackerman-recursive if it can be obtained from 0, σ, πik, and the Ackerman function A(n) by using composition and primitive recursion. Prove that there exists a computable function which is computable but not Ackerman-recursive.

7. (Due February 19) Show that the following function is mu-recursive: f(n) = 10 when n = 1, f(n) = 20 when n = 2, f(n) = 30 when n = 3, and f(n) is undefined for all other n.

8. (Due February 19) Show that division is mu-recursive -- similarly to how we showed in class that subtraction is mu-recursive.

9. (Due March 17) If A is r.e. and B is decidable, then what can we say about their union and intersection: are they r.e.? are they decidable? We thus have 4 questions:

• is union always r.e.?
• is union always decidable?
• is intersection always r.e.?
• is intersection always decidable?
For each of these four questions:
• if there is always the same answer (always yes or always no), prove it;
• if it is possible to have both "yes" and "no" answers, give examples when the answer is "yes" and when the answer is "no".

10. (Due March 17) Write down, in all needed details, a proof that a zero-checker is not possible. In precise terms, prove that no algorithm is possible that:

• given a program that always halts,
• checks whether this program always returns 0.

11. (Due March 17) Prove that factorial-checker is not possible. In precise terms, prove that no algorithm is possible that:

• given a program that always halts,
• checks whether this program returns n! for each input n.

12. (Due March 19) Design a Turing machine that computes π31; provide a step-by-step example of how this Turing machine works.

13. (Due March 19) Design a Turing machine that computes π32; provide a step-by-step example of how this Turing machine works.

14. (Due March 19) Use the general algorithm for composition to design a Turing machine that computes the composition σ(σ); provide a step-by-step example of how this Turing machine works.

15. (Due April 9) Submit a 1-2 page report on what you have done for your project so far.

16. (Due April 14) Illustrate step-by-step a general reduction of problems from the class NP to propositional satisfiability on the example of the following simple problem:

• given a string x,
• return a string y of the same length for which the following property C(x, y) is satisfied: the property that x =/= y.
Illustrate it on the example where x is a 1-bit string consisting of a single symbol 1.

Comment. This illustration should be similar to what we described in class, the only difference is that in class, we considering a different property C(x, y): the property that x = y.

17. (Due April 21) Take any formula in CNF and show how checking its satisfiability it can be reduced to checking satisfiability of a 3-CNF formula.

18. (Due April 21) Take any formula in 3-CNF and show how checking its satisfiability can be reduced to coloring a graph in 3 colors.

19. (Due April 21) Take any formula in 3-CNF and show how checking its satisfiability can be reduced to an instance of the subset sum problem (i.e., the problem of exact change).

20. (Due April 23) Take any formula in 3-CNF and show how checking its satisfiability can be reduced to an instance of the clique problem.

21. (Due April 23) Take any formula in 3-CNF and show how checking its satisfiability can be reduced to an instance of the interval computation problem.