Final exam: Tuesday Dec 8, 8:30 AM, Fowler 310. The exam will cover the whole semester (all HWs). You will not be tested on proving Theorems 1.3 & 1.4 of Sec 4.1 of Cutland.
HW 24, due F 11/20: Do these problems: Hopfield Network.
Midterm 3, M 11/16. It will cover HWs 16-24 18-23. You might find some of these links useful (I haven't looked at them carefully, though).
Here are some extra problems, for reviewing. These or similar problems may appear on the exam.
HW 23, due W 11/11: Read: Wilf: NP-completeness, and Sec 5.2 (p.107-111). Redo Sec 5.1 (p.109) 4abc using the "non-deterministic algorithm" definition of NP; explain and justify your work. For 4c, do not use the fact that primality testing is in P. Also do these problems.
HW 22, due F 11/6: Read: Wilf p.107. Do: Polynomial time reducibility.
Traveling Salesman Problem cartoon Dr Seuss proves undecidability of Halting Problem
HW 21, due W 11/4: Read: Wilf p.106-107 (up to "reducibility"). Do: Sec 5.1 (p.109): 4a-d. For 4cd, do not use the fact that primality testing is in P. Also do these problems.
HW 20, due M 11/2: Read: Wilf p.5-6 (may skip discussion on Omega). Do: Sec 1.1 (p.10): 2a-e, 8. Hint for #8: Look up Stirling's formula for n!. Read bottom half of p.24 (Sec 1.6), and definitions of path, simple path, cycle, circuit (p.25), and definitions of chromatic number, bipartite graph (p.27). Do: Sec 5.1 (p.109): 3ab.
HW 19, due F 10/30: Read: Wilf p.104-106. Do: Sec 5.1 (p.109): 1, 3cd. In your solutions state what you take as "input size" and as "one step".
HW 18, due W 10/28: Read Sec 0.1-0.2 (p.1-4) of Algorithms and Complexity, by Herbert S. Wilf . These two sections are not conceptually difficult; they may even seem too easy; but, to get a good perspective and preparation for the remainder of the semester, it's important that you understand them well. Do these problems. (We will cover mostly just Section 5 of Wilf.)
HW 17, due M 10/26: Read Sections 6.2-6.5. You won't be tested on these sections, but it's good to have some familiarity with them. Do these problems.
Some links on Game of Life and cellular automata:
Interactive Nice pictures of rules Wikipedia Turing Machine built in Game of Life SmoothLife
Wolfram: A new kind of science Scientific American article by Martin Gardener
HW 16, due F10/23: Do p.106: 1de. Also, resolve these two paradoxes: A Paradox on total, computable functions ; optional: A paradox on real numbers. Hints: Reduce 1d to the Halting Problem; reduce 1e to 1d (of course, these are not the only ways to do these problems).
Midterm 2, W 10/21: Will cover HWs 10-15 and their corresponding sections, plus proofs of Theorems 1.1 and 1.3 (Sec 6.1, p.101-103). Start reviewing as soon as you can.
HW 15, due F10/16. Read Sec 6.1 p. 100-103. Learn proofs (from book or class) of Theorems 1.1 and 1.3 (may be on exams). Do: p.106: 1c. Also do these problems. And prove Corollary 1.2 (p.101) without looking at the book's proof.
HW 14, due F 10/9. Read p. 85 and top of p. 86. Do these problems.
HW 13, due W10/7. Read Sec 4.3. Do: p.80: 2-4. Which of the following is the intended interpretation of #2? (a) Let f_0, f_1, f_2, ... be an enumeration of the set of all partial functions from N to N; (b) Let f_0, f_1, f_2, ... be an enumeration of a set of partial functions from N to N. Why?
Also do these problems.
HW 12, due M10/5. Read Sec 4.2. Do: 2.3 (p. 77). Also do these problems.
HW 11, due F 10/2. Read Sec 4.1 (p. 72-76); you may skip proofs of Theorems 1.3 & 1.4, and Example 1.5. Do: HW 11 problems.
HW 10, due M 9/28. Read Sec 3.7. Do: p.71: 1, 2. Also do these problems.
Midterm 1: Fri 9/25. The midterm will cover HWs 1-9, and their corresponding sections. You may be asked to give definitions. You will be given this paragraph on the midterm.
HW 9.5, due W 9/23: Read section 3.4. Do: page 57: 2ab (you may use the book's convention or class' convention for representing input and output; but say which one you're using). Also do these extra problems on recursion.
Just for fun: On the Ackermann function.
HW 9, due F 9/18. Read sections 3.1-3.3. May skip proofs of 2.2 and 2.3. Do these problems.
HW 8, due W 9/16. Read Section 2.5, including p. 46 (Ackermann function); may skip p. 47 and the proof of Theorem 5.2. Do: p.45-46: 1, 3. Also do these problems:
Q1. Prove or disprove: If f(x,y) is a total function, then mu z (f(x,z) = 0) is a total function.
Q2. Recall that C is defined in the book as the collection (or set) of all (URM) computable functions. What does it mean when the book says C is closed under minimalization?
Q3. The following questions refer to page 45, the block of text that starts with "Thus, in a trivial sense, ...".
(a) Explain that first sentence in your own words. (b) In the second sentence, what does "the use of the mu-operator is essential" mean?
Here's a Solution to Fibonacci problem.pdf
HW 7, due M 9/14. Read pages 40-41. Do: 1b-f, 2, 3, 4bc. In 1b, [x] denotes the floor function (i.e., round down; e.g., [5.8] = 5). For #2, do only the second half: show pi_1 and pi_2 are computable. Hints: 1d: gcd(x,y)lcm(x,y)=xy; 4b: use 1e.
Also do the following problem:
Q1: Suppose f(x) can be defined from the basic functions by substitution, recursion, and bounded minimalization. Can f(x) necessarily also be defined from the basic functions by substitution and recursion only (no bounded minimalization)? Explain why. (Hint: Which theorems and functions are used to prove that bounded minimalization is computable? See the proof in the book.)
HW 6, due F 9/11. Read the proof of Theorem 4.5, and pages 37-39. Do: Sec 4.2 (p. 41): 1a, 3, 4a. In Problem 4a, do not write a program; instead use Theorem 4.5; hint: use parts (f) or (g), and part (l) of the theorem. Also, provide details for the proofs of parts (g) and (h) of Theorem 4.5.
HW 5, due W 9/9. Read Section 2.4 up to and including Theorem 4.5; but may skip proof of Theorem 4.4. Do: p. 41 : 2(just show the map is a bijection). Give a detailed proof of Theorem 4.5, parts (a), (b), and (e). Also do the following problems. Do not write programs for them; you may use Theorem 4.5, as well as Problem 1 on page 32. (Hint: they only require substitution, not recursion.) Solutions
Prove the function f(x) = mx+n, where m and n are fixed natural numbers, is computable.
Prove that for every computable function h(x) and for every natural number n, the function (h(x))^n is computable.
Prove that the function h(x) = x^x^x is computable. (Note: a^b^c means a^(b^c), not (a^b)^c. This is standard convention.)
Prove that for every natural number n, the function h(x_1, x_2, ..., x_n) = x_1^x_2^...^x_n is computable (x_i means "x sub i"). Use mathematical induction.
HW 4, due F 9/4. Read Sections 2.1-2.2: Read p. 25 and top of p. 26 carefully; then just skim the rest of Sec 2.2. Read Theorem 3.1 on p. 29 (skip the proof). Read all of page 31, including Theorem 3.2 and its proof. Do: Sec 2.3: 3.4: 1, 2, 3 (do all these problems without writing any programs). For #1b, you may assume f(x,y)=x+y is computable (as in Example 3.3). For #3, you may assume the predicate "x=y" is decidable. Also do the following problems, and explain your reasoning for each.
Q1: Is there a URM program such that, when given input R1 = n, the program eventually stops with 1 in Rn? (The other registers can be anything.)
Q2: Is there a URM program such that, when given input 0 in all registers, eventually stops with a random output of 0 or 1 in R1? (The question is not whether you can write such a program; rather, whether you think such a program exists.)
HW 3, due W 9/2. Read Sections 1.4 & 1.5. Do: 4.3, 5.2(1); use the coding convention discussed in class for negative integers.
Optional: A contest, just for fun: What is the largest output you can produce with a URM program with only 10 instructions, starting with zeros in all registers? (In previous years, some students beat me at this contest by a large margin. I don't remember what the output was for the winning program, but I have it written down somewhere. You can work alone, or team up and share ideas.)
HW 2, due M 8/31. First read the bottom half of page 3 carefully (you may need to read it multiple times to get all the subtleties). Then read Sec 1.3. Do: p. 21-22: 1-4. Hint for #3: Use induction on the number of instructions.
HW 1, due F 8/28. Read Sections 1.1, 1.2. Here are pages 7-17, in case you don't have the book yet (get one ASAP). Do: Exercises 2.2, 2.3 (pages 14 and 16). Also, read and play with URM Simulator (if any of you are comfortable with Javascript, I need a volunteer to update this simulator for me please).