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

1. (Due January 29) Prove that the difference function diff(a, b) restricted to natural numbers is primitive recursive. This function is defined as follows: diff(a, b) = a − b if a is greater than or equal to b, and diff(a, b) = 0 otherwise.

2. (Due February 3) Prove that if P(n), Q(n), f(n), g(n), and h(n) are primitive recursive, then a complex if-then combination "if P(n) then f(n) elseif Q(n) then g(n) else h(n)" is also primitive recursive.

3. (Due February 5) Similarly to how we showed, in class, that the use of mu-recursion (while-loops) can simplify the description of subtraction, show how mu-recursion can also simplify the description of division.

4. (Draft due February 5; final proof by February 12) Write down the proof that we had in class, that there exists a computable function which is not primitive recursive. This proof must be a coherent text, with all the necessary words and explanations, not just formulas and abbreviations.

5. (Due February 10) Describe a mu-recursive function f(n) for which f(2) = 3, f(5) = 2, and f(n) is undefined for all other n.

6. (Due February 12; extra credit if submitted by February 10) A function is called Ackermann-primitive recursive if it can be obtained from 0, σ, πki, and the Ackermann function A(n) by using composition and primitive recursion. Prove that not every computable function is Ackermann-primitive recursive.

7. (Due February 12) Describe, in detail, a Turing machine for computing π32.

8. (Due February 12) Use a general algorithm for computing composition to combine the two Turing machines for computing the function σ into a single Turing machine for computing the composition f(n)=σ(σ(n)).

9. (Due February 17) Describe, in detail, a Turing machine for copying a pair. For example, for input (2, 3), this Turing machine shall produce a tuple (2, 3, 2, 3).

10. (Due February 19) Reproduce, in detail, the proof that we had in class: that it is not possible to have a halt-checker, i.e., that it is not possible possible to have an algorithm that:

• given a program p and data d,
• checks whether p halts on d.

11. (Due February 19) Reproduce, in detail, the proof that we had in class: that it is not possible to have a zero-checker, i.e., that it is not possible possible to have an algorithm that:

• given a program p which always halts,
• checks whether p always computes 0, i.e., whether p(n) = 0 for all n.

12. (Due February 19) Similarly to what we did in class with a square-checker, prove that it is not possible to have a cube-checker, i.e., that it is not possible possible to have an algorithm that:

• given a program p which always halts,
• checks whether p always computes the cube of the input, i.e., whether p(n) = n3 for all n.

13. (Due February 26, for extra credit) Try to solve all the problems from last year's Test 1.

14. (Draft due March 24; final submission due March 26) In the handout, it is explained what the algorithms generated in the proof that Satisfiability is NP-hard will produce for the following simplified problem: we start with a single bit x and we want to produce a bit y which satisfies the condition x = y. Use this example to show what will be produced if instead, we look for a bit y which satisfies a different condition: x & y.

15. (Due March 26) On an example of a CNF formula with disjunctions longer than 3, show how this formula will be reduced to 3-CNF.

16. (Due April 2) On the example of a formula (p \/ q) & (~p \/ q \/ r), show how satisfiability of this formula can be reduced to 3-coloring of the corresponding graph.

17. (Due April 2) Prove that the 5-coloring problem -- coloring a given graph in 5 colors -- is NP-hard.

18. (Due April 2) On the example of a formula (p \/ q) & (~p \/ q \/ r) & (p \/ q \/ ~r), show how satisfiability of this formula can be reduced to looking for a clique in the corresponding graph.

19. (Due April 2) On the example of a formula (p \/ q) & (~p \/ q \/ r) & (p \/ q \/ ~r), show how satisfiability of this formula can be reduced to the corresponding case of the subset sum (= exact change) problem.

20. (Due April 7) On the example of a formula (p \/ q) & (~p \/ q \/ r) & (p \/ q \/ ~r), show how satisfiability of this formula can be reduced to the main problem of interval computations.

21. (Due April 7) Show how to compute the largest 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?

22. (Due April 16) Solve Problems 7-9, 10, and 13 from last year's Test 2.

23. (Due April 21) Solve Problems 1, 2-6, and 11 from last year's Test 2.