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

Exclusions: MAT 309H, PHL 348H
Prerequisites for undergraduates: (CSC363H1/CSC463H1)/CSC365H1/CSC373H1/ CSC375H1/MAT247H1)

Announcements

Final marks have been submitted.
Grad students can pick up their final exam from my office (when I am in).
Students may email me to find their exam (and final) marks.

Lectures: MW 4 in MP 134

Tutorial: F12 in MP 134

Tutor: Robert Robere

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

Text: None. See Lecture Notes below.

Marking Scheme:

• 4 assignments worth 10% each (Due at beginning of tutorial Sept 29, Oct 20, Nov 17, Dec 1.)
• 1 closed-book test worth 20%: Oct 27
• final exam worth 40%

The work you submit must be your own.
You may discuss problems with each other; however
you should prepare written solutions alone.
Copying assignments is a serious academic offence and will be dealt with accordingly.

Click here for the course information sheet

Lecture Notes

• Notes pp1-18: Propositional Calculus (slightly revised)
• Notes pp18-30: Predicate Calculus (page 21, 3) clarified
• Notes pp31-38: Completeness of LK
• Notes pp39-53: Herbrand Theorem, Equality and Compactness
• Notes pp54-70: Computability Theory
• Notes pp71-82: Recursive and Recursively Enumerable Sets
• Notes pp83-95: Incompleteness and Undecidability Part I.
• Notes pp96-108: Peano Arithmetic
• Notes pp109-112: Godel's Incompleteness Theorems

Chapter's I and II in Logical Foundations of Proof Complexity by Cook and Nguyen
(available on line through the U of T library) closely follows pp 1 - 52 in the Notes.

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

• Pavel Pudlak: Logical Foundations of Mathematics and Computational Complexity `A Gentle Introduction.'
  This is full of interesting historical notes and philosophical comments.

Problem Sets (.pdf files)

• Problem Set 1 (2017)
• Problem Set 2 (2017)
• Problem Set 3 (2017)
• Problem Set 4 (2017)

• Midterm Test