Homeworks for the course CS 5315/CS 6315, Spring 2017

1. (Due January 24) Prove that the power function a^{b}
is primitive recursive. This proof should follow the same pattern
that we used in class to prove that addition and multiplication are
primitive recursive:

- You start with a 3-dot expression
- First you write a for-loop corresponding to this function
- Then you describe this for-loop in mathematical terms
- Then, to prepare for a match with the general expression for
primitive recursion, you rename the function to f and the
parameters to n
_{1}, ..., m - Then you write down the general expression of primitive recursion for the corresponding k
- Then you match: find g and h for which the specific case of primitive recursion will be exactly the functions corresponding to initialization and to what is happening inside the loop
- Then, you get a final expression for the function a
^{b}that proves that this function is primitive recursive, i.e., that it can be formed from 0, π^{k}_{i}, and σ by composition and primitive recursion.

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

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(σ(π^{2}_{1}),
add(π^{4}_{1}, π^{4}_{2},
π^{4}_{3}, π^{4}_{4}))),
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, σ,
π^{k}_{i}, 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:

- an example when the union A U B U C of the three sets is decidable,
- an example when the union A U B U C of the three sets is not decidable,
- an example when the intersection of the three sets is decidable, and
- an example when the intersection of the three sets is not decidable.

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 2^{n}.

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

- a Turing machine that computes g(n) = n + 1 and
- a Turing machine that computes a function f(n) which is equal to n − 1 when n ≥ 1 and 0 when n = 0.

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

- we go step-by-step until we find the first blank space,
- then, we replace this blank space with 1 and go back.

- start, # → working, R

(we start going to the right), - working, 1 → R

(we see 1, so we continue going), - working, # → 1, back, L

(we see a blank space, so we replace it with 1 and start going back), - back, 1 → L

(while we see 1s, we continue going back), - back, # → halt

(once we reach the very first cell, we stop).

- we go step-by-step until we find the first blank space,
- then, we go back, replace the last 1 with blank, and go back all the way.

- start, # →
testing, R

(we start going right), - testing, # → L,
halt

(if the first symbol we see is blank, this means that the original number was 0, so we go back and stop), - testing, 1
→ working, R

(if the first symbol we see is 1, we continue going right), - working, 1 → R

(as long as we see 1s, we go right), - working, # → ready, L

(when we see blank, we get ready to erase the last 1), - ready, 1 →
#, back, L

(we erase the last 1 and start going back), -
back, 1 → L

as long as see 1s, we continue going back), - back, # → halt

(once we are back where we started, we stop).

20. (Due March 7) In class, we design a Turing machine for
computing π^{2}_{1}. Use this design as a
sample to design a Turing machine for computing
π^{3}_{1}. 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
π^{2}_{1} is based on the following idea:

- we go step-by-step until we find the first blank space,
- when we see blank, this means that we are outside the 1st number, and we are going inside the second number, so we continue going right,
- when we see blank again, this means that we reached the end of the second number, so we go back and erase 1s one by one until we reach the blank space separating the 2nd number from the 1st one,
- after that, we stop erasing and simply go back.

- start, # → in1st, R,
- in1st, 1 → R,
- in1st, # → in2nd, R,
- in2nd, 1 → R,
- in2nd, # → erasing, L,
- erasing, 1 → #, L,
- erasing, # → back, L,
- back, 1 → L,
- back, # → halt.

21. (Due March 7) In class, we design a Turing machine for
computing π^{2}_{2}. Use this design as a
sample to design a Turing machine for computing
π^{3}_{2}. 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
π^{2}_{2} is based on the following idea:

- first, we place 1 in the very first cell, to make sure that we will know when to stop when we get back,
- then, one by one, we eliminate all the ones from the 1st number,
- then, we go to the second number and continue going until we reach the first blank space after its end,
- we need to move the second number closer to the starting cell,
- moving a unary number one step to the left means that we erase the last 1, and add a 1 before this number; this will keep the same number of ones, but we get one step closer to the starting cell of the Turing machine,
- so, once we reach the blank space after the second number, we go back one step, erase the 1 symbol, and start going left,
- we go left until we reach the end of the number, i.e., the first blank space, which we replace by 1,
- if right to the left of the replaced black space is a symbol 1, this means that we are at the starting cell of the Turing machine, thus we have moved the number already; now all we need to do is replace this symbol 1 with blank space and stop,
- on the other hand, if right to the left of the replaced blank space is an empty cell, this means that we need to again go right and repeat the same move-one-step-to-the-left procedure.

This Turing machine has the following main rules:

- start, # → 1, erase1st, R,
- erase1st, 1 → #, R,
- erase1st, # → right, R,
- right, 1 → R,
- right, # → erase, L,
- erase, 1 → #, left, L,
- left, 1 → L,
- left, # → 1, checking, L,

- erase, # → finish, L,
- finish, # → L,
- finish, 1 → #, halt.

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:

- the number N of states
q
_{0}, ..., q_{N − 1}; we assume that q_{0}is the start state, that the last-but-one state q_{N − 2}is the accept state, and the last state q_{N − 1}is the reject state; - the number M of
symbols s
_{0}, ... s_{M − 1}; we assume that s_{0}is the blank state _; - an integer array
state[n][m] that describes to what state the Turing machine moves
if it was in the state q
_{n}and sees the symbol s_{m}; - an integer array symbol[n][m] that describes
what symbol should be on the tape after the Turing Machine in the
state q
_{n}sees the symbol s_{m}(it may be the same symbol as before, or it may be some other symbol written by the Turing machine); - a character array lr[n][m] that
describes, for each state q
_{n}and for each symbol s_{m}, whether the Turing machine moves to the left (L), or to the right (R), or stays in place (blank symbol); - the integer array of a large size describing the original contents of the tape, i.e., what symbols are written in each cell.

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:

- start, _ --> inNumber, R
- inNumber, 1 --> state1, R
- inNumber, _ --> reject
- inNumber, 0 --> state0, R
- state0, 1 --> state1, R
- state0, 0 --> state0, R
- state1, 1 --> state1, R
- state1, 0 --> state0, R
- state1, _ --> reject
- state0, _ --> accept

- we have N =
7 states: q
_{0}= start, q_{1}= inNumber, q_{2}= state1, q_{4}= state0, q_{5}= accept, and q_{6}= reject; - we have M = 3 symbols:
s
_{0}= _, s_{1}= 0, and s_{2}= 1;

- The first rule start, _ --> inNumber, R means that state[0][0] = 1, symbol[0][0] = 0, and lr[0][0] = R.
- The second rule inNumber, 1 --> state1, R means that state[1][2] = 2, symbol[1][2] = 2, and lr[1][2] = R, etc.

24. (Due March 21) Give:

- an example of computation time
t
_{A}(x) for which the algorithm is practically not feasible, but is feasible according to the existing definition, and - an example of computation time t
_{A}(x) for which the algorithm is practically feasible, but is not feasible according to the existing definition.

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

- reviewing and reporting on a related paper, or
- doing some independent research (not research as in high school, but research as in graduate school, i.e., trying to come up with something new), or
- programming something theory-related.

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

- multiplication to addition and
- division to subtraction

- instead of directly
computing the product y = x
_{1}* x_{2}, we first compute X_{1}= ln(x_{1}) and X_{2}= ln(x_{2}), then compute Y = X_{1}+ X_{2}, and then y = exp(Y); - instead of directly computing the ratio
y = x
_{1}/ x_{2}, we first compute X_{1}= ln(x_{1}) and X_{2}= ln(x_{2}), then compute Y = X_{1}- X_{2}, and then y = exp(Y).

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:

- the first stack represents the symbol at the head's location and all the symbols after that, while
- the second stack represents all the symbols before the head.

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:

- given a bit x,
- find a bit y for which the following formula is true: ~x \/ y (where ~x means negation).

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 x_{1} * x_{2}
≥ x_{3}.

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
Σ_{3}P^{Π2P}?