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

1. (Due January 24) Prove that the power function ab 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 26) 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 January 26) Prove, from scratch -- i.e., based only on the definition of a primitive recursive function -- that remainder is primitive recursive. For that, you will also need to prove that if-then construction, addition, etc., are all primitive recursive.

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

5. (Due February 2) Write a Java program corresponding to the following primitive recursive function f = σ(PR(σ(π21), add(π41, π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 2) Show that the following function f(a, b) is μ-recursive: f(a, b) = a && b when a and b are both equal to either 0 or 1, and f(a, b) is undefined for other pairs (a, b).

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

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

9. (Due February 7) Let us define a function to be A-primitive recursive if it can be obtained from 0, σ, πki, and Ackermann's function A(n) by using composition and primitive recursion. Prove that there exists a computable function which is not A-primitive recursive. Hint: we need a minor modification of the proof in Problem 8.

10. (Due February 16) Prove that the function computed by the following while-loop is mu-recursive:

  int x = s;
  while(x < l || x > u)
    {x = (a * x + b) % N;}

11. (Due February 21, 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.

12-14. (Due February 21) Suppose that A, B are r.e. sets.

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

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

14. If a number n appears in the A-generating algorithm at moment 13, when will the deciding algorithm tell us that n is an element of the set A?

15. (Due February 23) 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:

16. (Due March 2) If you had any corrections on the proof that you submitted on January 31, redo and turn in a perfect proof that no algorithm is possible that, given a program p and data d, checks whether p halts on d.

17. (Due March 2, not for grading; due March 9 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.

18. (Due March 2) Prove that no algorithm is possible that, given a program p that always halts, checks whether this program always returns 2n.

19. (Due March 7) In class, we described two Turing machines:

In class, we used the general algorithm for designing a Turing machine for composition to design a Turing machine that computes the composition f(g(n)). The assignment is to use the same 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: This Turing machine has the following rules:

20. (Due March 7) In class, we design 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 (3, 2, 1).

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

This Turing machine has the following rules:

21. (Due March 7) In class, we design 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,2,1).

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:

22. (Due March 9) 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.

23. (Due March 9 for extra credit, March 21 for regular credit) 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:

24. (Due March 21) Give:

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

25. (Due March 21) Describe what project you plan to work on. As mentioned in the syllabus, a project can be:

The most important aspect of the project is that it should be useful and/or interesting to you.

26. (Due March 28) 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.

27. (Due March 28) The disadvantage of representing a tape as an array -- as in Problem 23 -- is that we have a limit on the words that we can emulate. A better way to simulate a Turing machine, as we mentioned in class, is to represent the contents of the tape as a pair of stacks:

Modify your program for simulating the Turing machine by using this two-stacks representation of a tape.

28. (Due April 11) 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:

29. (Due April 13) Take any formula in CNF and show how checking its satisfiability can be reduced to checking satisfiability of a 3-CNF formula.

30. (Due April 13) Take any formula in 3-CNF and show how checking its satisfiability can be reduced to coloring a graph in 3 colors.

31. (Due April 13) Take any formula in 3-CNF and show how checking its satisfiability can be reduced to an instance of the clique problem.

32. (Due April 13) Use the general algorithm to come up with DNF form and CNF form of the formula x1 * x2 ≥ x3.

33. (Due April 18) Take any formula in 3-CNF and show how checking its satisfiability can be reduced to an instance of the subset sum problem (i.e., the problem of exact change).

34. (Due April 20) Take any formula in 3-CNF and show how checking its satisfiability can be reduced to an instance of the interval computation problem.

35. (Due April 20) Show how to compute the sum of nine 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?

36. (Due April 20) If we take into account communication time, how fast can you compute the sum of n numbers in parallel?

37. (Due April 25) 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 0.01%? Give an example of a probabilistic algorithm. Why do we need probabilistic algorithms in the first place?

38. (Due April 25) Pick an example of an Ali-Baba problem, and explain, step by step, what solution two greedy algorithms will produce for this example.

39. (Due April 25 for extra credit, due April 27 for regular credit) 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).

40. (Due April 27 for extra credit, due May 4 for regular credit) What class of the polynomial hierarchy contains Σ3PΠ2P?