Logic and Computability

CSC 438/CSC2404 Winter 2023

Course Info

Instructor: Swastik Kopparty (swastik.kopparty@utoronto.ca)
Class Time and Place: Wednesdays 1pm-3pm, OISE 5150
Office Hours: Tuesdays 10:30am-11:30am
TA: Harry Sha, Deepanshu Kush
Tutorials: Friday 2pm-3pm, OISE 5150
TA Office hours: TBD

Please use the course piazza site for questions.

Text book: No required text. We will loosely follow Steve Cook's notes (available here). Other good references: Introduction to the Theory of Computation (by Sipser), Chapter by Buss on Proof theory (available here).

Please email me if you are not enrolled in the course and would like to sit in. Please email me if you are trying to enroll in the course and would like to be added to the course quercus site in the meantime.

This course will need comfort with proofs and mathematical precision.

Syllabus and course policies
Rough course outline:

Turing Machines, Recognizability, Decidability
Propositional Logic, Resolution, PK proof system
First order logic, LK proof system, Godel Completeness
Incompleteness, undecidability
Recursion theorem, applications to incompleteness
Miscellaneous advanced topics: eg. Undecidable problems from logic, the zero-one law for random graphs

Homeworks

On quercus page (via crowdmark).

Lectures

January 11: Turing Machines, recognizability, decidability, undecidability of
January 18: Propositional Logic, syntax, semantics, resolution
January 25: Completeness of resolution, PK proof system, completeness and soundness of PK
February 1: First order logic, vocabularies, structures/models, logical consequences
February 8: LK proof system
February 15: Completeness of the LK proof system, compactness, decidability of logical validity validity
February 22: NO CLASS (reading week)
March 1: the equality axioms, LK with equality, introduction to Peano arithmetic, introduction to Godel incompleteness
March 8: MIDTERM
March 15: the recursion theorem, capturing Turing machine computations with arithmetic, the incompleteness theorem for arithmetic
March 22: More incompleteness, problems even harder than recursively enumarable, Kolmogorov complexity
March 29: Unprovable statements from Kolmogorov complexity, Hilbert's 10 problem, the zero-one law for random graphs (notes)
April 5: Review for final exam