CSC 438F/2404F: Computability and Logic
Fall, 2006

The Undergrad Announcements (UGA) website contains announcements about things of importance to students, such as job and scholarship opportunities, academic and social events, and reminders of administrative deadlines.

Announcements

Click here to see the 2006 final exam that you just wrote.

See the final exams for this course for 2005.ps and 2003.ps

Lectures: MW 10 in BA 2135

Tutorial: F10 in BA 2135

Tutor: Phuong Nguyen

Instructor: Stephen Cook , email: sacook@cs, Office: Sandford Fleming 2303C, 416-978-5183
Office Hours: MW 11:15-12:00. Or make an appointment, or drop in.
QUESTIONS VIA EMAIL ARE WELCOME.

Text: None. See Lecture Notes below.

Marking Scheme:

• 5 assignments worth 10% each (Due at beginning of tutorial Sept 29, Oct 13, Nov 3, Nov 17, Dec 8)
• 2 closed-book tests worth 10% each (Oct 20, Nov 24)
• final exam worth 30%

Reference Link: Handbook of Proof Theory, Chapters I and II by Sam Buss

Other References:

• Herbert Enderton: A Mathematical Introduction to Logic . Academic Press, 1972.

• E. Mendelson: Introduction to Mathematical Logic . Wadsworth & Brooks/Cole, 1987

Lecture Notes (.ps files) These will be posted before each section of the course. They will be minor revisions of the notes available from the
2005 438 web page .

Please send corrections and comments to the instructor.

• Notes pp1-17: Propositional Calculus
• Notes pp18-30: Predicate Calculus
• Notes pp31-38: Completeness of System LK for Predicate Calculus
• Notes pp39-51: Herbrand Theorem, Equality, and Compactness
• Notes pp52-68: Computability Theory
• Notes pp69-80: Recursive and Recursively Enumerable Sets
• Notes pp81-93: Incompleteness and Undecidability Part I: Representing relations by formulas
• Notes pp94-106: Peano Arithmetic
• Notes pp107-110: Godel's Incompleteness Theorems

• Problem Set 1 Due Sept 29, in tutorial.
  
• Problem Set 2 Due October 13, in tutorial.
  
• Problem Set 3 Due Nov 3, in tutorial.
  
• Problem Set 4 Due Nov 17, in tutorial.
  
• CORRECTED Problem Set 5 Due Dec 8, in tutorial.
  (The correction: In Question 2b, Tarski's Theorem is on page 89 and the Undecidablilty Theorem is on page 104.)

• Test 1 October 20
  
• Test 2 November 24