Final exam, Friday 12/14, 1:00-4:00pm, Fowler 307. The exam will cover the whole semester. Here are the 2009 and 2006 final exams.
HW 24, due W 11/28: Do these problems: Hopfield Network.
Here's a Hopfield network simulator: http://www.phy.syr.edu/courses/CCD_NEW/mind/sim/hopfield.html
Mid 3. M 11/19. Will cover HWs 18-23 and their corresponding sections.
You might find some of these links useful (I haven't looked at them in detail, though).
Here are some extra problems, for reviewing. These or similar problems may appear on the exam.
HW 23, due M 11/12: Read: Wilf: NP-completeness, and Sec 5.2 (p.107-111). Redo Sec 5.1 (p.109) 4abd using the "ND algorithm definition" of NP; explain and justify your work. For 4d, do not use the fact that primality testing is in P. Also do these problems.
HW 22, due F 11/9: Read: Wilf p.107. Do: Polynomial time reducibility.
Traveling Salesman Problem cartoon Dr Seuss proves undecidability of Halting Problem
HW 21, due W 11/7: 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 the following: Wilf, page 107, line 13, says: "Any suggestions for a certificate?" Here's a suggestion: List all possible tours, and next to each, write its total length. This can be done algorithmically. This is my "certificate". Verifying the certificate is easy: add up the distances for each tour, and check that the total given for each tour in the list is correct; then check that none of these totals is less than K. Is there anything wrong with my certificate? Did I prove that the problem "There is no tour of length less than K" is in NP?
HW 20, part 2, due M 11/5: Polynomial Time Operations
HW 20, due F 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 W 10/31: 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 M 10/29: Read: Algorithms and Complexity, by Herbert S. Wilf Sec 0.1-0.2 (p.1-4). 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. (We will cover only a few sections of Wilf.) Do:
What does Wilf mean by an "easy" vs. a "hard" problem? By a "fast" vs. a "slow" algorithm?
Write a URM program that computes the function f(x,y) = xy; then give an upper bound for the number of steps your program takes as a function of input size x+y. Try your program in the URM Simulator to see if it works, and to see if your upper bound is accurate (the Output pane in the simulator shows the number of instructions performed).
Give an upper bound for the number of steps it takes to multiply an m-digit and an n-digit natural number using the algorithm we learn in elementary school. In your answer, explain what you consider as one "step".
Give an upper bound, as a function of input size m+n, for the number of steps your URM program (above) takes to multiply an m-digit and an n-digit natural number.
No HW due F 10/26. Just for fun: On the Ackermann function. More fun: If HP were decidable, would we be able to decide Goldbach's Conjecture? (It says: every even number is the sum of two primes.)
Mid 2, W 10/24. Will cover HWs 10-16 and their corresponding sections, plus proofs of Theorems 1.1 and 1.3 (Sec 6.1, p.101-103). Here's the 2009 Mid2; but it didn't cover the same sections and homework problems that ours will (mostly because of different timing); so don't spend too much time on it. Instead, redo as many of our homework problems as you can, without looking at the book or any notes. .
HW 17, due M 10/22: 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 the following problem (but don't turn it in): Suppose k is a fixed natural number such that the problem "x is in the domain of phi_k" is undecidable. Can we conclude that the problem "0 is in the range of phi_k" is undeciable? Justify your answer.
HW 16, due F 10/19: Do p.106: 1de. Also, resolve these two paradoxes: A Paradox on total, computable functions ; A paradox on real numbers.
HW 15, due W 10/17. 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 prove Corollary 1.2 (p.101) without looking at the book's proof.
Some links on Game of Life and cellular automata:
Interactive Nice pictures of rules Wikipedia SmoothLife
Wolfram: A new kind of science Scientific American article by Martin Gardener
HW 14, due W 10/10 F 10/12. Do these problems.
HW 13, due M 10/8. 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 the following problems, but do not turn them in.
Let f(x) = x (the identity function), and g(x) = x+2. According to the way we numbered URM programs in class (rather than the book's numbering), does f have an index less than 20? How about g? Why? (See page 77 for the definition of index.)
We proved in an earlier homework (p. 45, Problem 1) that the inverse of every total, injective, unary, computable function is computable. Show, using Church's Thesis, that the hypothesis of "total" is not necessary; i.e., prove that the inverse of every injective, unary, computable function is computable. Where do you use the hypothesis of "injective"?
Even if you can't prove the following, make sure you at least understand them well.
Show that if f : S --> S' is a bijection and S is denumerable, then S' is denumerable.
Given that every infinite subset of N is denumerable, show that every infinite subset of a denumerable set is denumerable.
HW 12, due F 10/5. Read Sec 4.2. Do: 2.3 (p. 77). Also do the following problems:
Determine whether each of the following functions is well-defined and computable. (For example, the following function is not well-defined, and hence not computable: h(x) = 1 if x = 0, h(x) = 2h(x+1) if x > 1.) Give clear and convincing arguments to support your answers. You may use Church's Thesis. You don't have to give rigorous proofs; just give as convincing an argument as you can.
f(x, y) = 1 if x = 0 or y = 0; f(x, y) = f(2x, y-1) + f(x-1, 2y) if x > 0 and y > 0.
g(x, y, z) = 1 if x = 0 or y = 0 or z = 0; g(x, y, z) = g(x-1,2y,2z) + g(x, y-1, 2z) + g(x, y, z-1) if x > 0 and y > 0 and z > 0. Hint: Define an ordering as follows: (x, y, z) < (x', y', z') iff x<x', or x=x' and y<y', or x=x' and y=y' and z<z'. (If you want a rigorous solution, here's a second hint.)
D(x) = 0 if x <= 1, D(x) = 1 + D(f(x)) if x > 1, where f(x) = x/2 if x is even, f(x) = 3x+1 if x is odd. How does D(x) compare to the function C(x) defined in HW #10? Hints
Remark: In many "modern" programming languages (such as C, Java, Mathematica, etc), all of the above functions (even the ones that are not well-defined) can easily be "implemented": you can write a program that mimics the definition of the function -- however, the program may never stop if the function is not well-defined.
HW 11, due W 10/3. 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.
Just for fun: On the Ackermann function.
HW 10, due M 10/1. Read Sec 3.7. Do: p.71: 1, 2. Also do the following problems:
Define f(x) as: x/2 if x is even, 3x+1 if x is odd. This function is called the Collatz function, named after its "inventor".
Prove f is computable (without using Church's Thesis).
Starting with x = 3, repeatedly apply the Collatz function f(x) defined above until you get 1 (i.e., find -- by hand -- f(3), then f(f(3)), then f(f(f(3))), and so on). How many times do you need to do this iteration?
Define C(x) as the smallest number z of iterations it takes to get f(...f(x)..) = 1, if such z exists; otherwise C(x) is undefined. Prove that C(x) is computable. Hint: Let g(x,n) = f(... f(x)...) , where f is iterated n times. Use recursion to show g is computable, and then conclude C is computable (without using Church's Thesis).
(It is unknown whether you eventually reach 1 for every starting value of x. No one has found any counterexamples, nor has anyone been able to prove that you always eventually reach 1. This is usually refered to as "the 3x+1 problem". If you solve it, you'll be very famous -- at least among mathematicians!)
Is C(x) in PR, R0, or R? Explain.
Mid 1, F 9/28. Midterm 1 will cover HWs 1-9 and their corresponding sections, and proofs of Theorem 4.5(a-k) and Corollaries 4.6 and 4.7 (p. 36-38). You may also be tested on definitions (e.g., def of basic functions, characteristic functions, bounded minimalization, minimalization, definition by recursion, primitive recursive, etc.). Most problems will be very similar to homework problems. A good way to study is to redo homework problems in a "closed book, closed notes" setting. Here's the 2009 midterm. Our midterm will be somewhat similar.
Solutions to Mid 1
HW 9, due M 9/24. Read sections 3.1-3.4. May skip proofs of 2.2 and 2.3. 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 problems.
HW 8, due F 9/21. 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/17 W 9/19. 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: 1b: first show ceiling(sqrt(x)) is computable; then express floor(sqrt(x)) in terms of ceiling(sqrt(x)); 1d: gcd(x,y)lcm(x,y)=xy; 4b: use 1e (x is a power of a prime iff exactly one prime number divides x).
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/14. 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/12. Read Section 2.4 up to and including Theorem 4.5; but may skip proof of Theorem 4.4. Do: Sec 2.4 (p. 42) : 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, but don't turn them in (you should know them for exams, though). 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.)
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 M 9/10. 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.)
Q3: Suppose I have written a URM program P. I won't show you my program; I only tell you that it has 100 instructions. Does there exist an N such that all registers after the Nth one will always contain 0?
HW 3, due F 9/7. Read Sections 1.4 & 1.5. Do: 4.3, 5.2(1); use the coding convention discussed in class for negative integers. Also think about, but do not turn in, this problem: Let f(n) = the largest possible output for a URM program with n instructions, starting with 0 in all registers. Is f computable?
HW 2, due W 9/5. 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: Sec 1.3 (p. 21-22): 1-4. Hint for #3: Use induction on the number of instructions.
Optional: Here's a contest to keep you entertained over Labor Day weekend: 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. Let's see if this class can beat all the previous classes!
HW 1, due F 8/31. 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.