1. (Due January 27) Prove that the function computing the sum 2 + 3 + ... + n + (n + 1) 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 February 1) Prove that if P(n), Q(n), R(n), f(n), g(n), h(n), and i(n) are all primitive recursive, then the function described as
3. (Due February 1) 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 3) Write a Java program corresponding to the following primitive recursive function f = σ(σ(PR(π^{2}_{2}, σ(add(π^{4}_{1}, π^{4}_{2}, π^{4}_{3}))))). For this function f, what is the value of f(1, 1, 1)?
5. (Due February 3 for extra credit, due February 8 for regular credit) Let us define a function to be σ-A-primitive recursive if it can be obtained from 0, σ, π^{k}_{i}, and a function σ(A(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-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 8) Show that the following function f(a, b, c) is μ-recursive: f(a, b, c) = a + b + c when each of the two inputs a and b is either equal to 0 or equal to 1, and f(a, b, c) is undefined for other triples (a, b, c)).
7. (Due February 8) Prove that the following function is mu-recursive:
int j = 1; while(!(a + j <= m)) {j++;}
8. (Due February 8, 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 10) Design a Turing machine that computes a function f(n) which is equal to n − 3 when n ≥ 3 and to 0 when n = 0, 1, or 2; it is OK to assume that the input n is given in unary code.
10. (Due February 15) In class, we designed a Turing machine for computing π^{2}_{1}. Use this design as a sample to design a Turing machine for computing π^{4}_{1}. Trace, step-by-step, on an example, how your Turing machine works. For example, you can take as input the triple (1, 2, 3, 4).
Reminder: The Turing machine for computing π^{2}_{1} is based on the following idea:
11. (Due February 15 for extra credit, due February 17 for the regular credit) In class, we designed a Turing machine for computing π^{2}_{2}. Use this design as a sample to design a Turing machine for computing π^{4}_{2}. Trace, step-by-step, on an example, how your Turing machine works. For example, you can take as input the tuple (1,2,3,4). 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 π^{2}_{2} is based on the following idea:
This Turing machine has the following main rules:
12. (Due February 15 for extra credit, due February 17 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 − 3 when n ≥ 3 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:
13. (Due February 15 for extra credit, due February 17 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 words in a 2-letter alphabet {a,b}. Test it on the example of a word bab. The result should be bab_bab, with a blank space in between. Hint: instead of marking 1s, mark both a's and b's; instead of the state carry1in1st, we can now have two different states: carryAin1st and carryBin1st.
14. (Due February 15 for extra credit, due February 17 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 + c;}No details are required, but any details will give you extra credit.
15. (Due February 15 for extra credit, due February 17 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 22) 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:
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:
17. (Due February 22) 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 8n^{2} + 5.
18-20. (Due February 24) Suppose that A, B are r.e. sets.
18. If a number n appears in the A-generating algorithm at moment 2, 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 2 and in the B-generating algorithm at moment 4, 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 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?
21. (Due February 24) Let us consider cases when the sets A and B are decidable and the set C is r.e. Give four examples of such cases:
22. (Due March 8) Give:
23. (Due March 8) Logarithms were invented to make multiplication and division faster: they reduce:
24. (Due March 10) Use the general algorithm to come up with DNF form and CNF form of the formula 0.3 * x_{1} + 0.5 * x_{2} ≥ 0.7 * x_{3}.
25. (Due March 10) 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:
26. (Due March 22) 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 22) 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 22) 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 22) 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 March 24) 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 5) Show how to compute the product 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 5) If we take into account communication time, how fast can you compute n! in parallel? Hint: See Section 2 of the paper with Dara Morgenstein on the class website.
33. (Due April 7) Suppose that we have a probabilistic algorithm that gives a correct answer 2/3 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 7) 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 7) 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 12) On the example of the function f(x) = x, trace, step by step, how Deutsch-Josza algorithm will conclude that f(0) ≠ f(1) while applying f only once.
37. (Due April 14) What class of polynomial hierarchy contains Σ_{2}P^{Π3P}? Explain your answer.
38. (Due April 19) 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 19) What can you say about the Kolmogorov complexity of the string 011011... in which the sequence 011 is repeated 2022 times?