10 % Class participation (send questions, answer questions,
contribute to discussion )
40 % Homework assignments (posted on calendar below)
50 % Final exam
Dates |
Reading assignment |
Topic | Homework/comments |
Week 0 Sept 4-5 |
Introduction | ||
Week 1 Sept 8-12 |
chapters 1-4 for Tuesday, Sept 9 | effective computability, formal languages, Wff 'n' Proof | |
Week 2 Sept 15-19 |
chapters 4-5 for Tuesday, Sept 16 | formal theories, negation completeness,
capturing/expressing numerical properties |
Homework 1 due
Friday Sept 19 Homework 1 Solutions |
Week 3 Sept 22-26 |
read again Ch. 5 chapter 6 (7-8) for Tuesday, Sept 23 |
sufficiently expressive, a first
incompleteness
theorem |
|
Week 4 Sept 29 - Oct 3 |
chapters 7-8-9-10 for Tuesday, Sept 30 |
induction, baby arithmetic, Q |
Homework 2 due
Friday Oct 3 tex file for homework 2 Homework 2 solutions |
Week 5 Oct 6-10 |
chapters 11-12 for Tuesday, Oct 7 |
bounded quantifiers, limited induction |
|
Week 6 Oct 13-17 |
chapters 13-14 for Tuesday, Oct 14 |
Peano Arithmetic, primitive recursion |
Thanksgiving Monday Oct 13 Homework 3 due Friday Oct 17 tex file for homework 3 |
Week 7 Oct 20-24 |
chapters 15-16 for Tuesday, Oct 21 |
expressing primitive recursive functions |
|
Week 8 Oct 27-31 |
chapters 17, 19 for Tuesday, Oct 7 | Q captures primitive recursive; godel
numbering |
Midterm recess Oct 30, 31 Homework 4 due Tuesday Nov 4 (but recommended for Oct 29) tex file for homework 4 |
Week 9 Nov 3-7 |
chapters 20-21 for Tuesday, Nov 4 |
more on coding; incompleteness of Peano
Arithmetic and the Goedel theorem! |
|
Week 10 Nov 10-14 |
chapters |
Goodstein's theorem is true but not provable |
Homework 5 due
Friday Nov 14 tex file for homework 5 |
Week 11 Nov 17-21 |
chapter 25 for
Tuesday, Nov 18 read
chs 30, 41
and 44 |
Rosser's
theorem Turing machines and Turing computability, mu-computability and equivalence with Turing computability |
|
Week 12 Nov 24-28 |
chapter 31 for Tuesday, Nov 25 read ch 38, 42 | examples of undecidable problems |
Homework 6 due
Wednesday Dec 3 tex file for homework 6 |
Week 13 Dec 2-3 |
Julia Robinson movie |