CSC438 Logic and Computation, Fall 2026
\[% Shared mathematical notation for CSC438. % % Keep this file limited to commands supported by both LaTeX and MathJax. % Quarto loads it through filters/shared-macros.lua; TeX preambles can use % \input{../macros} when compiled from a first-level project directory. \renewcommand{\subset}{\subseteq} \renewcommand{\iff}{\leftrightarrow} \newcommand{\N}{\mathbb{N}} \newcommand{\proves}{\vdash} \newcommand{\cA}{\mathcal{A}} \newcommand{\cF}{\mathcal{F}} \newcommand{\cL}{\mathcal{L}} \newcommand{\cP}{\mathcal{P}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\TR}{\mathbf{TR}} \newcommand{\D}{\mathbf{D}} \newcommand{\R}{\mathbb{R}} \newcommand{\seq}{\Rightarrow} \newcommand{\RA}{\Longrightarrow} \newcommand{\LRA}{\Longleftrightarrow} \newcommand{\OI}{\{0,1\}} \renewcommand{\SS}{\Sigma^*} \newcommand{\powerset}{\mathcal{P}} \newcommand{\blank}{\sqcup} \newcommand{\angles}[1]{\left\langle #1\right\rangle} \newcommand{\enc}[1]{\left\ulcorner #1\right\urcorner} \newcommand{\Lang}{\mathcal{L}} \newcommand{\Th}{\operatorname{Th}} \newcommand{\Thm}{\operatorname{Thm}} \newcommand{\Prov}{\operatorname{Prov}} \newcommand{\Con}{\operatorname{Con}} \newcommand{\ATM}{A_{\mathrm{TM}}} \newcommand{\HALTTM}{\operatorname{HALT}_{\mathrm{TM}}} \newcommand{\HALTe}{\operatorname{HALT}_{\epsilon}} \newcommand{\AExp}{A_E} \newcommand{\AMult}{A_M} \newcommand{\green}[1]{\textcolor{green}{#1}} \newcommand{\red}[1]{\textcolor{red}{#1}} \newcommand{\st}[1]{\sout{#1}} \]
Welcome to the CSC438 website! You can find all the information and course materials here.
Getting started
Weekly Schedule
| Week | Date | Topic | Assessment | Links |
|---|---|---|---|---|
| 1 | September 7, 2026 | Introduction, Countability, Turing Machines | ||
| 2 | September 14, 2026 | Decidability and Undecidability | ||
| 3 | September 21, 2026 | Recursion Theorem / Self Reference | ||
| 4 | September 28, 2026 | Propositional Logic, Resolution, PK | TT1 | |
| 5 | October 5, 2026 | Propositional Soundness/Completeness/Compactness | ||
| 6 | October 12, 2026 | First-order Logic, LK, Soundness | ||
| 7 | October 19, 2026 | Completeness / Compactness | ||
| 8 | October 26, 2026 | Reading week! | ||
| 9 | November 2, 2026 | Incompleteness | TT2 | |
| 10 | November 9, 2026 | Incompleteness | ||
| 11 | November 16, 2026 | Kolmogorov Complexity and Chaitin’s Incompleteness | ||
| 12 | November 23, 2026 | ZFC | TT3 | |
| 13 | November 30, 2026 | Extra topic / review |
Slides
- Intro and countability. slides, +scribbles
- Computability. slides, +scribbles
- Propositional Logic. slides, +scribbles
Course Calendar
Resources
The lecture slides are the main resource for this course.
Some additional useful resources are the following:
- Sipser — Introduction to the Theory of Computation
- Enderton — A Mathematical Introduction to Logic
- Steve Cook’s Course Notes