Fall, 2016

** Announcements **

Week of Oct 24: Read NOTES on Computability Theory

Midterm Test in tutorial Oct 28: Covers NOTES pp 1 - 53.

See link at bottom of page for last year's csc 438h, including
test and problem sets.

See below for solutions to Problem Set 2.

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.

Michael Sipser:

** 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
- Solutions to Problem Set 2

Click here for last year's CSC 438h, including problems sets and tests.