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

1. (Due January 27) 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 January 27) Translate, step-by-step, the following primitive recursive expression into a for-loop: PR(add(π21, π22), σ(π44)). Provide an explicit formula for the corresponding function.

3. (Due January 27) Prepare a preliminary topic for your class project.

4. (Due February 1) Prove, from scratch (i.e., based only on the definition of a primitive recursive function), that integer division a / b is primitive recursive.

5. (Due February 1) 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 1, 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 8.

6. (Due February 3) Prove that division is mu-recursive, similar to how we proved, in class, that subtraction is mu-recursive.

7. (Due February 3) Translate the following while-loop into a mu-recursive expression:

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

8. (Due February 3) Translate the following mu-recursive expression into Java code: μc.(add(a,c) ≥ b), where add = PR(π11, σ(π33)).

9. (Due February 8) Write down a proof that there exists a computable function which is not primitive recursive. This time, the proof must be absolutely correct.

10. (Due February 8) If A is r.e. and B is decidable, is their union r.e.?is it decidable? is their intersection r.e.? decidable?

11. (Due February 8) Write down, in all needed details, a proof that zero-checker is not possible. Please try to make this proof as complete and clear as possible; it is Ok if there are some minor faults or gaps in your description. The final (absolutely correct) version of this proof is due on February 15.

12. (Due February 8) Prove that a cube-checker is not possible. To be more precise, prove that no algorithm is possible that, given a program p that always halts, check whether this program always computes n3.

13. (Due February 8) Write down the rules of a Turing machine that computes 0 based on a binary input. Trace your Turing machine step-by-step on the example of input 012 (i.e., 01 in binary code). Please do not forget to take into account that we assume that the binary number is stored in the Turing machine starting with the lowest bit (in the given example, with 1).

14. (Due February 10, extra credit if returned by February 8) Write down the rules of a Turing machine that computes the function π31. You can assume that numbers are given in unary code. Trace your Turing machine on the example of a triple (2,2,1).

15. (Due February 10) Design a Turing machine for computing the function π32. Provide a step-by-step example of how this machine works.

16. (Due February 10) Use the general algorithm for composition to design a Turing machine that computes a function f(n) = (n + 1) + 1; assume that the input n is given in binary code.

17. (Due February 15) Write down, in all needed details, a proof that zero-checker is not possible. This time the proof must be absolutely correct.

18. (Due February 15) Give two examples:

• an example when an algorithm is feasible in the sense of the formal definition but not practically feasible, and
• an example when an algorithm is practically feasible, but not feasible according to the formal definition.
These examples must be different from the examples that we had in class.

19. (Due February 15) Similarly to a Turing machine that we had in class, that copies a number in unary code, design a Turing machine that copies a binary number. Test it on the example of a binary number 110 (stored as 011). The result should be 110_110, with a blank space in between. Hint: instead of marking 1s, mark both 0s and 1s; instead of state carry, we can now have two different states: carry0 and carry1.

20. (Due February 15) For the Turing machine that you designed in Problem 16, trace how it works for n = 1. Describe, for each step, how the corresponding state of the Turing machine can be represented as two stacks, and what pops and pushes are involved in each transition.

21. (Due February 22) Logarithms were invented to make multiplication and division faster: they reduce:

• division to subtraction
by using the formulas ln(x1 * x2) = ln(x1) + ln(x2) and ln(x1 / x2) = ln(x1) − ln(x2). Specifically:
• instead of directly computing the product y = x1 * x2, we first compute X1 = ln(x1) and X2 = ln(x2), then compute Y = X1 + X2, and then y = exp(Y);
• instead of directly computing the ratio y = x1 / x2, we first compute X1 = ln(x1) and X2 = ln(x2), then compute Y = X1 - X2, and then y = exp(Y).
Describe each of these two reductions in general terms: what is C(x, y), what is C'(x', y'), what is U1, U2, and U3.

22. (Due March 2) Submit progress report on your class project.

23. (Due March 16) 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: x implies 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 considered a different property C(x, y): the property that x = y.

24. (Due March 23) Take any formula in CNF and show how checking its satisfiability can be reduced to checking satisfiability of a 3-CNF formula.

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

26. (Due March 28) 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).

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

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

29. (Due April 4) Show how to compute the product of eight numbers in parallel if we have an unlimited number of processors. How many processors do we need and how much time will this computation take? Why do we need parallel processing in the first place?

30. (Due April 4) If we take into account communication time, how fast can you compute the product of n numbers in parallel?

31. (Due April 6) Suppose that we have a probabilistic algorithm that gives a correct answer half of the time. How many times do we need to repeat this algorithm to make sure that the probability of a false answer does not exceed 1%? Give an example of a probabilistic algorithm. Why do we need probabilistic algorithms in the first place?

32. (Due April 11) Pick an example of an Ali-Baba problem, and explain, step by step, what solution two greedy algorithms will produce for this example.

33. (Due April 13) Solve problems 4-12 from last year's Test 3.

34. (Due April 25) Use the variable-elimination algorithm for checking satisfiability of 2-SAT formulas that we had in class to find the values that satisfy the following formula:
(a \/ ~b) & (~a \/ b) & (~a \/ ~b) & (a \/ ~c) & (~a \/ ~c) & (b \/ ~c).

35. (Due May 2) What class of the polynomial hierarchy contains Σ2PΠ2P?