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