THEORY OF COMPUTATION
Homeworks for the course CS 5315, Spring 2008

1. Prove that the function n^2 is primitive recursive.

2. Prove that the function n^3 is primitive recursive.

3. Prove that an arbitrary polynomial is primitive recursive.

4. 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 h(n)" is also primitive recursive.

5. (For extra credit) Prove that the relations <=, >=, and = are primitive recursive.

6. Write down a detailed proof that not every computable function is primitive recursive.

7. In class, we proved that Ackermann's function A(n) is not primitive recursive. Let us therefore define a function to be A-primitive recursive if it can be obtained from 0, projection ("pi"), next ("sigma"), and A(n) by using composition and primitive recursion. Prove that there exists a computable function which is not A-primitive recursive.

8. Describe division in terms of mu-recursion.

9. Describe a mu-recursive function f(n) for which f(n)=2 when n=0, f(n)=3 when n=1, and f(n) is undefined for all other n.

10. Design a Turing machine that computes pi^3_1, i.e., that takes a triple as an input, and returns the first element of this triple.

11. Design a Turing machine that computes pi^3_2, i.e., that takes a triple as an input, and returns the second element of this triple; trace this Turing machine to check that it is correct.

12. Write down a detailed proof that halting problem is undecidable.

13. Write down a detailed proof that zero-checker is not possible.

14. Proof that a cube-checker is not possible, i.e., that it is not possible to have an algorithm that given a program p, returns "true" if this program always correctly computes n^3.

15. For an arbitrary expression, use the algorithm described in class to produce CNF and DNF forms.

16. Write down the proof that satisfiability is NP-hard.

17. Describe what you have done so far for your project.

18. Trace the proof that satisfiability is NP-hard on the example of a 1-bit problem.

19. Illustrate a reduction from satisfiability to clique on an example of a simple propositional formula.

20. Illustrate a reduction from satisfiability to 3-CNF on an example of a simple propositional formula.

21. Illustrate a reduction from satisfiability to graph coloring on an example of a simple propositional formula.

22. Illustrate a reduction from satisfiability to interval computations on an example of a simple propositional formula.

23. Illustrate a reduction from satisfiability to subset sum on an example of a simple propositional formula.

24. Explain how multiplication of two 4 by 4 matrices can be parallelized.