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

1. (Due January 29) Prove that the function an is primitive recursive.

2. (Due January 29) Prove that the function n3 + n2 + 5 is primitive recursive.

3. (Due January 29) Prove that the function n3 - n2 + 5 is primitive recursive.

4. (Due January 29) Prove that the Exclusive Or operation is primitive recursive.

5. (Due February 3) 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) else if Q(n) then g(n) else h(n)" is primitive recursive.

6. (Due February 5) Write down, in detail, the proof that not every computable function is primitive recursive.

7. (Due February 10, 2009) Submit a project proposal.

8. (Due February 10, 2009) Let us define an A-p.r. function as a function that can be obtained from 0, ++, projections, and the Ackermann function A(n) by using composition and primitive recursion. Prove that there exists a computable function which is not A-primitive recursive.

9. (Due February 10, 2009) Find a simple proof that division is mu-recursive.

10. (Due February 10, 2009) Prove that the following function f(n) is mu-recursive: it is equal to 1 when n = 2, it is equal to 2 when n = 1, and it is undefined for all other n.

11. (Due February 12, 2009) Reproduce the proof of the halting problem that we had in class.

12. (Due February 12, 2009) Reproduce the proof that zero-checking is impossible, the proof that we had in class.

13. (Due February 12, 2009) By a cube-checker, we mean a program that, given a program p that always halts, returns "yes" if p(n) is always equal to n3 and "no" otherwise. Prove that cube-checkers are impossible.

14. (Due February 17, 2009) Design a Turing machine that computes the function n+2.

15. (Due February 17, 2009) Design a Turing machine that computes the function π31.

16. (Due February 17, 2009; for extra credit) Design a Turing machine that computes the function π22.

17. (Due February 19, 2009) Design a Turing machine that computes the function π32.

18. (Due February 24, 2009) Take any two Turing machines and use the method that we described in class to design a single Turing machine that computes the composition of the corresponding functions.

19. (Due February 24, 2009) Prove that if the sets A and B are decidable, then their intersection is also decidable.

20. (Due March 30, 2009) Solve all the problems from 2007 Test 1.

21. (Due March 30, 2009) Report on the progress of your project.

22. (Due April 9, 2009, for extra credit) Similarly to the proof we had in class, show how the problem of finding y for which x implies y can be reduced to propositional satisfiability.

23. (Due April 14, 2009) On an example of a CNF formula, show it can be reduced to 3-CNF.

24. (Due April 14, 2009) On an example of a 3-CNF formula, show how the corresponding propositional satisfiability problem can be reduced to graph coloring.

25. (Due April 14, 2009, for extra credit) Prove that the problem of coloring a graph in 5 colors in NP-hard.