General comments.

• Solutions to the homeworks should be submitted to the instructor as attachments to an email. If your solution is on paper, scan it and send the scanned file. Make sure that the instructor's computer can read the this file. In general, pdf, jpeg, and many other general formats are OK, the instructor will let you know if the format is not readable.
• When submitting a homework, please add its number to the email subject. Please use the same number as in this list of homeworks.
• In general, for full credit, homeworks need to be submitted before 4:30 pm on the due date. You can submit your solutions after the deadline -- but before the solutions are posted. In general, points will be taken off for late submissions. The only two exception are:
  • students who have a special CASS permission to submit solutions at any time before the solutions are posted, and
  • students who have a legitimate reason to be late; if you have such a reason, let the instructor know; once the instructor approves late submissions. you can then submit your solutions until the homeworks are posted.
  In these two cases, there will be no penalty for later submissions.
• In general, solutions to the homeworks that are due on the day of a class will be posted right after the next class:
  • if a homework is due on Monday, the solutions will be posted on Wednesday, and
  • if a homework is due Wednesday, the solutions will be posted next Monday.
  Once the correct solutions are posted, student answers will no longer be accepted. The only exception is programming assignments: there will be no posted solutions to these assignments, so you can submit solutions to these assignments any time -- with the corresponding penalty for late submissions.
• Things happen. If there is an emergency situation and you cannot submit your solution before the solutions are posted, let the instructor know, the instructor will then make sure that your overall grade for the homeworks is not affected by this situation.
• Homeworks are an indicator how well students understand the material. The instructor is not supposed to help solve the assigned homeworks, but the instructor is always willing to show how to solve a similar problem.

• 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₁, ..., 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 * 1 + 1) * (2 * 2 + 2) * (3 * 3 + 3) * ... * (n * n + n) 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.

Solutions to Homework 1

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

Comment. Here, !P, as usual in Java, mean negation.

Solutions to Homework 2

3. (Due February 11) 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 is primitive recursive.

Solutions to Homework 3

4. (Due February 11) Use the general algorithm for translation from the PR expression back into Jana to write a Java program corresponding to the following primitive recursive function F = σ(σ(PR(0, sum(π²₂, π²₁)))). For this function F, what is the value of F(2)?

Solutions to Homework 4

5. (Due February 16) Let us define a function to be (A*n)-primitive recursive if it can be obtained from 0, σ, π^k_i, and a function A(n) * n (where A(n) is Ackermann's function) by using composition and primitive recursion. Prove that there exists a computable function which is not (A*n)-primitive recursive. Hint: we need a minor modification of the first (detailed) proof that there exists a computable function which is not primitive recursive.

Solutions to Homework 5

6. (Due February 18) 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 undefined for other pairs (a, b).

Solutions to Homework 6

7. (Due February 18) Use the general algorithm for translating programs with while-loops into mu-recursive expressions to prove that the following function is mu-recursive:

  int j = a;
  while(!(j + b > c))
    {j++;}

Solutions to Homework 7

8. (due February 18) Describe integer division a / b in terms of μ-recursion, similarly to how in the lecture, we describe subtraction in terms of μ-recursion.

Solutions to Homework 8

9. (Due February 23) Design a Turing machine that computes a function f(n) which is equal to n − 4 if n > 4 and to 0 if not; assume that the input n is given in unary code.

Solutions to Homework 9

10. (Due March 9) In class, we designed a Turing machine for computing π²₁. Use this design as a sample to design a Turing machine for computing π³₁ for tuples of unary numbers. Trace, step-by-step, on an example, how your Turing machine works. For example, you can take as input the triple (2, 1, 3).

Reminder: The Turing machine for computing π²₁ for tuples of unary numbers 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, -- → R, in1st
• in1st, 1 → R
• in1st, -- → R, in2nd
• in2nd, 1 → R
• in2nd, -- → L, erasing
• erasing, 1 → --, L
• erasing, -- → L, back
• back, 1 → L
• back, -- → halt.

Solutions to Homework 10

11. (Due March 9) In class, we designed a Turing machine for computing π²₂. Use this design as a sample to design a Turing machine for computing π⁴₃ for tuples of unary numbers. Trace, step-by-step, on an example, how your Turing machine works. For example, you can take as input the tuple (2,1,1,1). 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 π²₂ for tuples of unary numbers 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.

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,

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

Solutions to Homework 11

12. (Due March 11) In class, we described a Turing machine that computes g(n) = n + 1 for unary numbers. In Homework 9, you designed a Turing machine that computes a function f(n) which is equal to n − 4 when n > 4 and to 0 otherwise -- also for the case of unary numbers.

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)) for unary n. Trace, step-by-step, on an example, how your Turing machine works. For example, you can take as input n = 1.

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 two 1s with blanks, and go back all the way.

Solutions to Homework 12

13. (Due March 9) Similarly to a Turing machine that we had in class, that copies a number, design a Turing machine that copies words consisting of letters m and n. Test it on the example of a word mn. The result should be mn_mn, with a blank space in between. Hint: instead of marking 1s, mark both m's and n's; instead of the state carry1in1st, we can now have two different states: carry_m_in1st and carry_n_in1st.

Solutions to Homework 13

14. (Due March 9 for extra credit, due March 11 for 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

  v = a;
  for(int i = 1; i <= b; i++)
    {v = v * i;}

Solutions to Homework 14

15. (Due March 9 for extra credit, due March 11 for 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.

Solutions to Homework 15

16. (Due March 11) 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 n³ − n.

Solutions to Homework 16

17. (Due March 11) 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.

Solutions to Homework 17

18. (Due March 23) To solve an equation a * y⁶ + b * y³ + c = 0, a natural idea is to introduce a new variable z = y³ for which we will have a quadratic equation -- an equation that we know how to solve. Describe the resulting reduction in general terms: what is C(x, y), what is C'(x', y'), what is U₁, U₂, and U₃.

Solutions to Homework 18

19. (Due March 23) Write and test a method that simulates a general Turing machine. Your program should enable the computer to simulate any given Turing machine for accepting-rejecting and then to simulate, for any given word, step-by-step, how this Turing machine decides whether this word is accepted or not.

The input to this method should include:

• the number N of states q₀, ..., q_{N − 1}; we assume that q₀ 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₀, ... s_{M − 1}; we assume that s₀ 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 simulate 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 = 6 states: q₀ = start, q₁ = inNumber, q₂ = state1, q₃ = state0, q₄ = accept, and q₅ = reject;
• we have M = 3 symbols: s₀ = _, s₁ = 0, and s₂ = 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.

20-22. (Due April 1) Suppose that A, B are r.e. sets.

20. 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?

Solutions to Homework 20

21. If a number n appears in the A-generating algorithm at moment 4 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?

Solutions to Homework 21

22. 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?

Solutions to Homework 22

23. (Due April 1) Let us consider cases when the set A is decidable and the complements to the sets B and C are r.e. Give four examples of such cases:

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

Solutions to Homework 23

24. (Due April 13) Use the general algorithm to come up with DNF form and CNF form of the formula 0.6 * x₁ + 0.4 * x₂ ≥ 0.3 * x₃.

Solutions to Homework 24

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

Solutions to Homework 25

26. (Due April 15) 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.

Solutions to Homework 26

27. (Due April 15) 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.

Solutions to Homework 27

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

Solutions to Homework 28

29. (Due April 15) 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.

Solutions to Homework 29

30. (Due April 20) 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 20) Show how to compute the "or" of 14 boolean values 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 20) If we take into account communication time, how fast can you compute the peoduct 1 * 1/2 * ... * 1/n in parallel? Hint: See Section 2 of the paper with Dara Morgenstein on the class website.

• There, we show that T_sequential ≤ (T_parallel)⁴.
• So what can we tell about T_parallel? That T_parallel is bounded, from below, by the fourth order root of T_sequential.

33. (Due April 22) Suppose that we have a probabilistic algorithm that gives a correct answer 7/8 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 5%? Explain your answer. Give an example of a probabilistic algorithm. Why do we need probabilistic algorithms in the first place?

34. (Due April 22) 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 22) 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 22) What can you say about the Kolmogorov complexity of the string 10001000... in which the sequence 1000 is repeated 2026 times?

37. (Due April 27) 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.

38. (Due May 4) What class of polynomial hierarchy contains Σ₂P^Π₂P? Explain your answer.

39. (Due May 4) Describe, in detail, at least three different schemes that use serious but still hypothetical physical processes to solve NP-complete problems in polynomial time.