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 45 
Introduction  
Week 1 Sept 812 
chapters 14 for Tuesday, Sept 9  effective computability, formal languages, Wff 'n' Proof  
Week 2 Sept 1519 
chapters 45 for Tuesday, Sept 16  formal theories, negation completeness,
capturing/expressing numerical properties 
Homework 1 due
Friday Sept 19 Homework 1 Solutions 
Week 3 Sept 2226 
read again Ch. 5 chapter 6 (78) for Tuesday, Sept 23 
sufficiently expressive, a first
incompleteness
theorem 

Week 4 Sept 29  Oct 3 
chapters 78910 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 610 
chapters 1112 for Tuesday, Oct 7 
bounded quantifiers, limited induction 

Week 6 Oct 1317 
chapters 1314 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 2024 
chapters 1516 for Tuesday, Oct 21 
expressing primitive recursive functions 

Week 8 Oct 2731 
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 37 
chapters 2021 for Tuesday, Nov 4 
more on coding; incompleteness of Peano
Arithmetic and the Goedel theorem! 

Week 10 Nov 1014 
chapters 
Goodstein's theorem is true but not provable 
Homework 5 due
Friday Nov 14 tex file for homework 5 
Week 11 Nov 1721 
chapter 25 for
Tuesday, Nov 18 read
chs 30, 41
and 44 
Rosser's
theorem Turing machines and Turing computability, mucomputability and equivalence with Turing computability 

Week 12 Nov 2428 
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 23 
Julia Robinson movie 