# 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