Theory of Computation
Homeworks for the course CS 5315/CS 6315, Spring 2020

1. (Due January 30) Prove that the factorial function n! is primitive recursive. This proof should follow the same pattern that we used in class to prove that addition and multiplication are primitive recursive:

2. (Due January 30) Prove that if P(n), Q(n), f(n), g(n), and h(n) are all primitive recursive, then the function described as

if P(n) then f(n) elseif Q(n) then g(n) else h(n)
is also primitive recursive.

3. (Due February 4, not for grading) Write down, in all the detail, the proof that we had in class: that there exists a computable function which is not primitive recursive.

4. (Due February 6) Prove, from scratch -- i.e., using only the definition of the primitive recursive function (and not using any results that we had in class without proving them) -- that the division function is primitive recursive.

5. (Due February 6) Write a Java program corresponding to the following primitive recursive function f = σ(PR(π22, σ(add(π42, π43, π44)))), where add is the usual addition: add(a, b, ...) means a + b + ... For this function f, what is the value of f(2, 0, 2)?

6. (Due February 11) Show that the following function f(a, b) is μ-recursive: f(a, b) = !a || !b when each of the two inputs a and b is either equal to 0 or equal to 1, and f(a, b) is undefined for other pairs (a, b).

7. (Due February 11) Prove that the following integer version of the logarithm function -- computed by the following while-loop -- is mu-recursive:

  int j = 1;
  while(!(pow(a,j) >= m))
    {j++;}

8. (Due February 11, for extra credit) Describe integer division a / b in terms of μ-recursion, similarly to how we describe subtraction in terms of μ-recursion.

9. (Due February 13) If you had any corrections on the proof that you submitted on February 6, redo and turn in a perfect proof that there exists a computable function which is not primitive recursive.

10. (Due February 13) In the first proof, we provided an example of a function f(n) which is computable but not primitive recursive. Let us define a function to be f-primitive recursive if it can be obtained from 0, σ, πki, and the above-mentioned function f(n) by using composition and primitive recursion. Prove that there exists a computable function which is not f-primitive recursive. Hint: we need a minor modification of the proof in Problem 3.

11. (Due February 13) Design a Turing machine that computes a function f(n) which is equal to n − 2 when n ≥ 2 and to 0 when n = 0 or 1; it is OK to assume that the input n is given in unary code.

12. (Due February 13) In class, we designed a Turing machine for computing π21. Use this design as a sample to design a Turing machine for computing π31. Trace, step-by-step, on an example, how your Turing machine works. For example, you can take as input the triple (1, 3, 2).

Reminder: The Turing machine for computing π21 is based on the following idea:

This Turing machine has the following rules:

13. (Due February 18) In class, we designed a Turing machine for computing π22. Use this design as a sample to design a Turing machine for computing π32. Trace, step-by-step, on an example, how your Turing machine works. For example, you can take as input the triple (3,1,2). Also, check also that your code works when one of the numbers is 0, especially when the third number is 0.

Reminder: The Turing machine for computing π22 is based on the following idea:

A special care needs to be taken for a special case when the second component of the original pair is number 0. In this case, once we erase the 1st number, there is nothing left to erase, so we simply go back (and replace 1 back to blank when we reach the starting cell).

This Turing machine has the following main rules:

The following three additional rules take care of the case when the second number is 0:

14. (Due February 18) In class, we described a Turing machine that computes g(n) = n + 1. In homework 11, you designed a Turing machine that computes a function f(n) which is equal to n − 2 when n ≥ 2 and 0 when n = 0.

In class, we described the general algorithm for designing a Turing machine that computes the composition of two functions. The assignment is to use this general algorithm to design a Turing machine that computes the composition g(f(n)). Trace, step-by-step, on an example, how your Turing machine works. For example, you can take as input n = 2.

Reminder: The Turing machine for computing g(n) = n + 1 for a unary input n is based on the following idea:

This machine has the following rules: The Turing machine for computing f(n) is based on the following idea: We need to take special care of the case when n = 0

15. (Due February 18) 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 1011 (stored as 1101). The result should be 1101_1101, 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.

16. (Due February 25) Write a method that emulates a general Turing machine. The input to this method should include:

This program needs to keep track of a current location of the head. Initially, this location is 0.

Your program should emulate the work of the Turing machine step-by-step. Return the printout of the method, the printout of the program that you used to test this method, and the printout of the result of this testing. Feel free to use Java, C, C+++, Fortran, or any programming language in which the code is understandable.

Example: A Turing machine for checking whether a binary string is even (i.e., ends with 0) has the following rules:

In this case: Here:

17. (Due February 27) Sketch an example of a Turing machine for implementing primitive recursion (i.e., a for-loop), the way we did it in class, on the example of the following simple for-loop

  sum = a;
  for(int i = 1; i <= b; i++)
    {sum = sum + 2;}
No details are required, but any details will give you extra credit.

18. (Due February 27) Sketch an example of a Turing machine for implementing mu-recursion, the way we did it in class, on the example of a function μm.(m + 1 = 3). No details are required, but any details will give you extra credit.

19. (Due March 3, not for grading) Write down a proof that we had in class: that no algorithm is possible that, given a program p and data d, checks whether p halts on d.

20. (Due March 3, not for grading) Write down a proof that we had in class: that no algorithm is possible that, given a program p that always halts, checks whether this program always returns 0.

21. (Due March 3) Use the impossibility of zero-checker (that we proved in class) to prove that no algorithm is possible that, given a program p that always halts, checks whether this program always computes 3n+2.

21'-23. (Due March 5) Suppose that A, B are r.e. sets.

21'. If a number n appears in the A-generating algorithm at moment 3, when will this number appear in the algorithm generating all elements of the union A U B?

22. If a number n appears in the A-generating algorithm at moment 2 and in the B-generating algorithm at moment 3, when will this number appear in the algorithm generating all elements of the intersection of A and B?

23. If a number n appears in the A-generating algorithm at moment 3, and the complement −A is also r.e., when will the deciding algorithm tell us that n is an element of the set A?

24. (Due March 10) Let us consider cases when the set A is decidable and the sets B and C are r.e. Give four examples of such cases:

25-26. (Due March 10) If you had any corrections to any of the two proofs that you submitted on February 27, redo and turn in a perfect proof(s).

27 (Due March 12) Give:

These examples must be different from the ones we had in class.

28. (Due March 12) Logarithms were invented to make multiplication and division faster: they reduce:

by using the formulas ln(x1 * x2) = ln(x1) + ln(x2) and ln(x1 / x2) = ln(x1) − ln(x2). Specifically: 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.

29. (Due March 31) Use the general algorithm to come up with DNF form and CNF form of the formula 0.3 * x1 + 0.5 * x2 ≥ 0.8 * x3.

30. (Due April 7) Similar to what we did in the class, illustrate the general algorithm of reducing NP problems to satisfiability on the example of the following problem:

Solution to Problem 30

31. (Due April 9) On the example of the formula (a \/ b \/ ~c \/ ~d) & (~a \/ ~b \/ ~c), show how checking its satisfiability can be reduced to checking satisfiability of a 3-CNF formula. See 31.pdf for the corresponding lecture; a somewhat different proof is presented in Corollary 7.42 of the book (2nd edition).

Solution to Problem 31

32. (Due April 9) On the example of the formula (a \/ b \/ ~c) & (~a \/ ~b), show how checking its satisfiability can be reduced to coloring a graph in 3 colors. See 32.pdf for the corresponding lecture; see also Exercise 7.27 of the book (2nd edition).

Solution to Problem 32

33. (Due April 9) On the example of the formula (a \/ b \/ ~c) & (~a \/ ~b), show how checking its satisfiability can be reduced to an instance of the clique problem. See 33.pdf for the corresponding lecture; see also Theorem 7.32 from the book (2nd edition).

Solution to Problem 33

34. (Due April 9 for extra credit, due April 14 for regular credit) On the example of the formula (a \/ b \/ ~c) & (~a \/ ~b), show how checking its satisfiability can be reduced to an instance of the subset sum problem (i.e., the problem of exact change. See 34.pdf for the corresponding lecture; see also Theorem 7.56 from the book (2nd edition).

Solution to Problem 34

35. (Due April 14) On the example of the formula (a \/ b \/ ~c) & (~a \/ ~b), show how checking its satisfiability can be reduced to an instance of the interval computation problem. See 35.pdf for the corresponding lecture.

Solution to Problem 35

36. (Due April 16) Show how to compute the product of 12 numbers in parallel if we have unlimited number of processors. How many processors do we need and how much time will the computation take? Why do we need parallel processing in the first place? See 36.pdf for the corresponding lecture; see also Section 40.5 of the book (2nd edition).

Solution to Problem 36

37. (Due April 16) If we take into account communication time, how fast can you compute the product of n numbers in parallel? Hint: See Section 2 of the paper with Data Morgenstein on the class website.

For the product problem, Tsequential = n.

Solution to Problem 37

38. (Due April 21) 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 3%? Explain your answer. Give an example of a probabilistic algorithm. Why do we need probabilistic algorithms in the first place? See 38.pdf for the corresponding lecture.

Solution to Problem 38

39. (Due April 21) Pick an example of an Ali-Baba problem, and explain, step by step, what solution two greedy algorithms will produce for this example. See 39.pdf for the corresponding lecture.

40. (Due April 21) 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). See handout on 2-CNF formulas posted on the class website.

Solution to Problem 40

41. (Due April 23) On the example of the negation function f(x) = ~x, trace, step by step, how Deutsch-Josza algorithm will conclude that f(0) =/= f(1) while applying f only once. See handout on quantum computing posted on the class website.

Solution to Problem 41

42. (Due April 28) What class of polynomial hierarchy contains Σ2PΠ3P? Explain your answer. See 42.pdf for the corresponding lecture.

Solution to Problem 42

43. (Due April 30) Describe, in detail, at least two different schemes that use serious but still hypothetical physical processes to solve NP-complete problems in polynomial time; see corresponding handouts.

Solution to Problem 43