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

1. (Due January 30) Write a program that simulates a Turing machine. For extra credit: make the program show, step-by-step, how the state of the Turing machine changes in the course of computations.

2. (Due January 30) Prove that the functions ab and n! are primitive recursive.

3. (Due February 4) Prove that if P(n), f(n), Q(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 4) Prove that a function n5 + 3n + 2 is primitive recursive.

5. (Due February 6) Write down a proof that not every computable function is primitive recursive. You will get full credit for submitting a proof even if the proof is not perfect, the main idea is to get a feedback so that we can go over the proof again in the next class.

6. (Due February 11) Write down how to describe division in terms of μ-recursion.

7. (Due February 11) Show that the following function f(n) is μ-recursive:

• f(n) = 100 when n = 5;
• f(n) = 80 when n = 4;
• f(n) is undefined for all other n.
8. (Due February 11) Use your general Turing machine program to simulate a Turing machine that always returns 0.

9. (Due February 11, for extra credit) Use your general Turing machine program to simulate a Turing machine that adds 1 to a number in binary code.

10. (Due February 13) Write down a proof that not every computable function is primitive recursive; this time, make sure that the proof is correct.

11. (Due February 13) Use your general Turing machine program to simulate a Turing machine that computes π22; we described this machine in class. For simplicity, feel free to restrict it to numbers in unary code.

12. (Due February 13) Design a Turing machine that computes π32.

13. (Due February 18) Use a general algorithm for designing a Turing machine for computing a composition to design a Turing machine that computes the composition f(g(n)) of functions f(n) = n + 1 and g(n) = n + 1.

14. (Due February 18) Following the idea that we had in class, show how a Turing machine would compute the value f(n1, ..., nk) = μm.P(n1, ..., nk, m) for the case when the value of this function is 2.

15. (Due February 20) In the main proof that not every computable function is primitive recursive, we use the diagonal construction to construct a function which is computable but not primitive recursive. Let us denote this function by d(n). Let us add this function to the list of basic functions. We say that a function is d-primitive recursive if it can be constructed from 0, σ, πki, and d(n) by using composition and primitive recursion. Prove that not every computable function is d-primitive recursive.

16. (Due February 20) Write down a proof that no algorithm is possible that checks whether a given program p halts on given data d. You will get full credit for submitting a proof even if the proof is not perfect, the main idea is to get a feedback so that we can go over the proof again in the next class.

17. (Due February 20) Write down a proof that no algorithm is possible that, given a program p which always halts, checks whether this program always returns 0. You will get full credit for submitting a proof even if the proof is not perfect, the main idea is to get a feedback so that we can go over the proof again in the next class.

18. (Due February 20) Write down a proof that no algorithm is possible that, given a program p which always halts, checks whether this program always returns n!. You will get full credit for submitting a proof even if the proof is not perfect, the main idea is to get a feedback so that we can go over the proof again in the next class.

19. (Due February 25; you get extra credit if you do it by February 20) Prove that no algorithm is possible that, given a program p which always halts, checks whether this program always returns n5.

20. (Due February 27) Write down a proof that no algorithm is possible that checks whether a given program p halts on given data d; this time, make sure that the proof is correct. No need to redo the proof if it was correct the first time around, you will automatically get full credit.

21. (Due February 27) Write down a proof that no algorithm is possible that, given a program p which always halts, checks whether this program always returns 0; this time, make sure that the proof is correct. No need to redo the proof if it was correct the first time around, you will automatically get full credit.

22. (Due February 27) Write down a proof that no algorithm is possible that, given a program p which always halts, checks whether this program always returns n!; this time, make sure that the proof is correct. No need to redo the proof if it was correct the first time around, you will automatically get full credit.

23-24. (Due February 27) Let f(n) be any function. This function does not have to be computable. For example, it can describe the results of measuring temperature at moment n. We can say that a function p(n) is f-computable if it can be computed by a program that calls a method f. An example of an f-computable function is a function p(n) = 2 * f(n) + n3. We can then define a set S to be

• f-decidable if there an f-computable function that, given a natural number n, checks whether n belongs to the set S or not, and
• f-recursively enumerable (f-r.e., for short) if there is an f-computable program that eventually generates all elements of the set S (and only these elements).

23. Prove that if sets A and B are f-decidable, then their union and intersection are also f-decidable.

24. Prove that if sets A and B are f-r.e., then their union and intersection are also f-r.e.

25. (Due March 4, for extra credit) Solve problems from last year's Test 1.

26. (Due March 25) Use the general algorithm to transform the following relation to DNF and CNF forms: 0.5 * x1 + 0.4 * x2 <= 0.4.

27. (Due March 27) Illustrate the general proof that Propositional Satisfiability is NP-hard on the example of a slightly different NP problem than what we had in class: in the new problem, the input is still one bit x, but the problem is to find a bit y for which C(x, y) is true, where this time, C(x, y) means x implies y.

28. (Due April 3) On an example of a propositional formula in 3-CNF, show how the reduction algorithm that we learned in class will reduce the corresponding propositional satisfiability problem to the problem of finding a clique of a given size in a given graph:

• draw and briefly describe the corresponding graph G;
• show how a satisfying vector for the original formula leads to a clique in the graph G, and, vice versa, how a clique in the graph G leads to a satisfying vector.

29. (Due April 3) On an example of a propositional formula in 3-CNF, show how the reduction algorithm that we learned in class will reduce the corresponding propositional satisfiability problem to the problem of coloring a graph in 3 colors:

• draw and briefly describe the corresponding graph G;
• show how a satisfying vector for the original formula leads to a coloring of this graph G in 3 colors and, vice versa, how a coloring of the graph G in three colors leads to a satisfying vector.

30. (Due April 8) On an example of a propositional formula in 3-CNF, show how the reduction algorithm that we learned in class will reduce the corresponding propositional satisfiability problem to the exact change problem:

• describe the corresponding exact change problem;
• show how a satisfying vector for the original formula leads to a possibility to represent the given amount S by some of the given coins, with values s1, ..., sn and, vice versa, how a solution to this exact change problem leads to a satisfying vector.

31. (Due April 8) Prove that the problem of coloring a graph in 5 colors is NP-hard.

32. (Due April 10) On an example of a propositional formula in 3-CNF, show how the reduction algorithm that we learned in class will reduce the corresponding propositional satisfiability problem to a problem of interval computations:

• describe the corresponding interval computation problem;
• show how a satisfying vector for the original formula leads to a solution to the interval computation problem, and, vice versa, how a solution to the interval computation problem leads to a satisfying vector.

33. (Due April 10) Take an example of two classes C and C' from the polynomial hierarchy, and describe the class CC'.

34. (Due April 10) Show how the maximum of n numbers can be computed in parallel if we have an unlimited number of processors (and if we ignore communication time). Describe the schemes for n = 2, 4, and 8; in each case, explain how many processors we need, and how many cycles. In general, for n = 2k, describe how many processors and how many cycles we need.

35. (Due April 30) 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%?

36. (Due May 1, for extra credit) Solve problems from last year's Test 2.