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

1. (Due January 26) Prove that the function computing the sum 1 + 2 + ... + 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:

• 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 n1, ..., 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 1 + 2 + ... + n that proves that this function is primitive recursive, i.e., that it can be formed from 0, πki, and σ by composition and primitive recursion.

2. (Due January 28) 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 2) 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 function a / b + a % b is primitive recursive.

4. (Due February 2) Write a Java program corresponding to the following primitive recursive function f = σ(PR(π22, σ(add(π41, π42, π43)))). For this function f, what is the value of f(0, 2, 2)?

5. (Due February 2 for extra credit, due February 4 for regular credit) 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 first proof that there exists a computable function which is not primitive recursive.

6. (Due February 4) 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 4) Prove that the following function is mu-recursive:

```  int j = 1;
while(!(a * j <= m))
{j++;}
```

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

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

10. (Due February 11) 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:

• 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.
This Turing machine has the following rules:
• start, -- → R, in1st
• in1st, 1 → R
• in1st, -- → R, in2nd, R
• in2nd, 1 → R
• in2nd, -- → L, erasing
• erasing, 1 → --, L
• erasing, -- → L, back
• back, 1 → L
• back, -- → halt.

11. (Due February 11 for extra credit, due February 16 for the regular credit) 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 (1,3,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:

• 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 directly 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 directly 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.
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:

• 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,
• checking, -- → right, R,
• checking, 1 → -- , halt,
The following three additional rules take care of the case when the second number is 0:
• erase, -- → finish, L,
• finish, # → L,
• finish, 1 → -- , halt.

12. (Due February 11 for extra credit, due February 16 for the regular credit) In class, we described a Turing machine that computes g(n) = n + 1. In Homework 9, 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:

• we go step-by-step until we find the first blank space,
• then, we replace this blank space with 1 and go back.
This machine has the following rules:
• 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).
The Turing machine for computing f(n) is based on the following idea:
• we go step-by-step until we find the first blank space,
• then, we go back, replace the last two 1s with blanks, and go back all the way.
We need to take special care of the case when n = 0.

13. (Due February 11 for extra credit, due February 16 for the regular credit) 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 1101 (stored as 1011). The result should be 1011_1011, with a blank space in between. Hint: instead of marking 1s, mark both 0s and 1s; instead of the state carry1in1st, we can now have two different states: carry0in1st and carry1in1st.

14. (Due February 11 for extra credit, due February 16 for the regular credit) 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 + a;}
```
No details are required, but any details will give you extra credit.

15. (Due February 11 for extra credit, due February 16 for the regular credit) 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 = a). No details are required, but any details will give you extra credit.

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

• the number N of states q0, ..., qN − 1; we assume that q0 is the start state, that the last-but-one state qN − 2 is the accept state, and the last state qN − 1 is the reject state;
• the number M of symbols s0, ... sM − 1; we assume that s0 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 qn and sees the symbol sm;
• an integer array symbol[n][m] that describes what symbol should be on the tape after the Turing Machine in the state qn sees the symbol sm (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 qn and for each symbol sm, 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.
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:

• 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
In this case:
• we have N = 6 states: q0 = start, q1 = inNumber, q2 = state1, q3 = state0, q4 = accept, and q5 = reject;
• we have M = 3 symbols: s0 = _, s1 = 0, and s2 = 1;
Here:
• 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.

17. (Due March 2) 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 5n + 8.

18-20. (Due March 4) Suppose that A, B are r.e. sets.

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

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

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

21. (Due March 4) 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.

22. (Due March 9) Give:

• an example of computation time tA(x) for which the algorithm is practically not feasible, but is feasible according to the existing definition, and
• an example of computation time tA(x) for which the algorithm is practically feasible, but is not feasible according to the existing definition.
These examples must be different from the ones we had in class.

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

• division to subtraction
by using the formulas ln(x1 * x2) = ln(x1) + ln(x2) and ln(x1 / x2) = ln(x1) − ln(x2). Specifically:
• instead of directly computing the product y = x1 * x2, we first compute X1 = ln(x1) and X2 = ln(x2), then compute Y = X1 + X2, and then y = exp(Y);
• instead of directly computing the ratio y = x1 / x2, we first compute X1 = ln(x1) and X2 = ln(x2), then compute Y = X1 − X2, and then y = exp(Y).
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.

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

25. (Due March 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 ~y means negation).

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

27. (Due March 23) 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.

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

29. (Due March 23) 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.

30. (Due April 6) 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.

31. (Due April 8) Show how to compute the sum of 11 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?

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

• There, we show that Tsequential ≤ (Tparallel)4.
• So what can we tell about Tparallel? That Tparallel is bounded, from below, by the fourth order root of Tsequential.
For the sum problem, Tsequential = n.

33. (Due April 13) Suppose that we have a probabilistic algorithm that gives a correct answer 3/4 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?

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

35. (Due April 13) 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).

36. (Due April 15) On the example of the function f(x) = 1, trace, step by step, how Deutsch-Josza algorithm will conclude that f(0) = f(1) while applying f only once.

37. (Due April 20) What class of polynomial hierarchy contains Σ4PΠ1P? Explain your answer.

38. (Due April 20) Describe, in detail, at least two different schemes that use serious but still hypothetical physical processes to solve NP-complete problems in polynomial time.

39. (Due April 22) What can you say about the Kolmogorov complexity of the string 001001... in which the sequence 001 is repeated 2020 times?