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

Announcements

Problem Set 2 is due Friday (Oct 21) beginning of tutorial.

Week of Oct 17: Finish Predicate Calculus Notes (pp 48 - 53) and begin Notes "Computability Theory" pages 54 - 59.

Solutions to PS 1 and Markers Comments are now posted below.

ANNOUNCEMENT:

==================================
Accessibility Services needs dependable volunteer note-takers to assist students living with a disability to achieve academic success!!
Volunteers report that by giving to the U of T community their class attendance and note taking skills improve.
All you have to do is attend classes regularly and submit them consistently.
Step 1: Register Online as a Volunteer Note-Taker
here.
Step 2: Select your course and click Register
Step 3: Upload your notes after every class
Typed notes can be submitted online. Legible Hand-Written notes can be scanned and uploaded at your home or at our office. Please see our office location and hours below.
Accessibility Services (Note-taking Program) 455 Spadina Avenue, 4th Floor Room 400
Office Hours: 9:00 AM-4:00 PM (Monday to Friday) Daily Office closure 12:30 PM - 1:30 PM
Email us at as.notetaking@utoronto.ca or call 416-978-6186 if you have questions or require any assistance.
Volunteers may receive co-curricular credit or a certificate of appreciation.
Thank you for you support.
=====================================

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.

Lectures: MW 4 in SS 2106

Tutorial: F12 in SS 2106

Tutor: Lalla Mouatadid

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 30, Oct 21, Nov 18, Monday Lecture Dec 5.)
• 1 closed-book test worth 20%: Oct 28
• final exam worth 40%

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.

Lecture Notes

Please send corrections and comments to the instructor.

• 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

Problem Sets (.pdf files)

• Problem Set 1
• Solutions to Problem Set 1
• Markers comments on Problem Set 1
• Problem Set 2