Computer Science 67XX -- Computability and Logic, Fall 2011

Announcements | Course information | Important dates | Assignments and tests | Lecture notes


29/08/2011 The first lecture is as scheduled, at 15:30 on Thursday, September 8th. Please email me if you would like to take this course, but have a scheduling conflict!


Course information

Course Information Sheet

Lectures: 3:30-5pm Tuesdays and Thursdays in EN-1002
Instructor: Antonina Kolokolova , email: [Your browser cannot view this email address] , office ER-6033.

No textbook is required for the course. I will be posting lecture notes; you can check out the lecture notes for a similar course at the University of Toronto.
Useful reference books would be:

Description: What is solvable? What is provable? And what do we mean by being solvable and provable? These are fundamental philosophical questions, with a practical importance to match. In this course, we will study classical unprovability resuts such as Goedel Incompleteness Theorem, and relate them to unsolvability results such as the Halting problem undecidability. More specifically, we will cover general computability (recursive and primitiverecursive functions, undecidability, etc), propositional and predicate logic, theories of arithmetic with the emphasis on Peano arithmetic, and many beautiful theorems: Goedel completeness and incompleteness theorems, compactness theorem, Lowenheim-Skolem theorem, Paris-Harrington theorem about unprovability of a natural combinatorial statement in Peano arithmetic... Time permitting, we will also look at some modern proof complexity and bounded arithmetic.