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

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

Sorry -- there seems to be a bug in the script that allows you to find your mark.

Click here to check unofficial final marks.
Your unofficial final mark is labelled "finl". For grad students, convert to a letter grade using the standard conversion table, given in the grad calendar.

Click here to see the final exam.
(Grad students may pick up their marked final exams.)

Lectures: MW 10 in SS 1088

Tutorial: F10 in SS 1088

Tutors: Dustin Wehr and Kaveh Ghasemloo

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 26, Oct 10, Oct 31, Nov 14, Dec 5)
• 2 closed-book tests worth 10% each (Oct 17, Nov 21)
• 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
2006 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 LK
• Notes pp39-53: Herbrand Theorem,
• Notes pp54-70: Computability Theory
• Notes pp71-82: Recursive and
• Notes pp83-95: Incompleteness and Undecidability Part I.
• Notes pp96-108: Peano Arithmetic (Corrected Nov 26: Minor typos fixed; especially the bottom formula on page 100 and in the statement of the MAIN LEMMA page 101 the unions should be intersections.)
• Notes pp109-112: Godel's Incompleteness Theorems

• Problem Set 1 Due September 26
• Problem Set 2 Due Oct 10
• Problem Set 3 Due October 31
• Problem Set 4 Due Nov 14
• Problem Set 5 Due Dec 5

• Test 1 October 17