| HW # | Due Date | Read | Do |
|---|---|---|---|
| -- | Tue 8 May | Final Exam | |
| 15 | Wed 2 May | Pages.123-4, 126, + Theorems 2.3, 2.6, 2.7, 2.9, 2.14. | p. 132: 2, 5, 7, 8. |
| 14 | Wed 25 Apr | Page 121, + Theorem 1.3 on page 122.. | p. 119: 5, 7(b,c -- don't have to use book's hints
or methods; use Church's Thesis to just prove the conclusions). p. 122: 1(a). |
| 13 | Mon 23 Apr | Section 6.6. | p. 119: 1, 3, 4. |
| 12 | Wed 18 Apr | Section 6.3 (page 107). | p. 106: 1bcdeh. |
| 11 | Mon 16 Apr | Section 6.1. (For proofs that use the s-m-n Theorem or the universal function, try to modify them to use Church's Theorem only.) | p. 106: 1afgi, 2. |
| -- | Wed 4 Apr | Midterm #2 | |
| -- | Mon 2 Apr | Work on Practice Midterm #2 | Nothing to turn in. |
| 10 | Wed 28 Mar | Review for Midterm #2, Wed 4/4/01. | p. 94: 1-4. (For all these problems, use Church's Thesis to give informal proofs.) |
| 9 | Wed 14 Mar | Pages 85-86. | p. 90: 1(iii), 2. (For both problems, use Church's Thesis to give informal proofs; or for 1(iii), prove (i) and (ii).) |
| 8 | Mon 12 Mar | Pages 72-73, 79-80, + handout: Counting Programs | See bottom of page 2 of handout: Counting Programs |
| 7 | Mon 5 Mar | Section 3.7 | p. 71: 1-4. |
| -- | Mon 26 Feb | Midterm #1: Covers Chapters 1 and 2. Practice Midterm #1 | (Postponed from Wed 21 Feb) |
| 6 | Wed 21 Feb | Pages: 48-9, 52-57 | p. 57: 1, 2. |
| 5 | Wed 14 Feb -- Postponed to Wed 21 Feb | Section 2.5: Minimalization. | p. 45: 1, 3. |
| 4 | Mon 12 Feb -- Postponed to Wed 14 Feb | Section 2.4 again: Recursion; bounded minimalization. | p. 41: 1(d,e), 2, 3, 4(b,c). |
| 3 | Wed 7 Feb | Sections 1.4: Decidability, 2.4: Recursion | p. 23: 4.3; p.32: 3. p. 41: 1(a,b,c). |
| 2 | Mon 5 Feb | Sections 2.1-2.3: Joining programs; substitution. | 3.4; p. 32: 1, 2. |
| 1 | Fri 2 Feb | Sections 1.1-1.3 URM-computable functions. | 2.2, 2.3; p. 21: 3.3: [1abc], 1def, 2-4. |
Square Brackets [ ] mean "do but don't turn in". These are usually easier problems that make for good warm-up or practice exercises. You are expected to know how to do them but don't need to write them up and turn them in.
CH: Challenge Problems are optional. If you do them, do not turn them in with your regular homework; instead come show them during office hours. These are problems that are interesting and sometimes more challenging; but you are not responsible for them.