Session 15: Computability, Decidability & What Hardness Means
Overview
The limits of computation: what cannot be decided at all, what can be decided but not efficiently, and why the distinction matters for proof assistants.
Lecturer
Wissam El Daouk (CSE)
Session Information
- Date and Time: Monday 16 November 2026 — 17:30-19:30
- Place: (to be announced)
- Online Meeting Link
- Session Recording
Core Concepts
- Computable functions: primitive recursion, composition, and the μ-operator; partial and general recursive functions (OLP 29)
- A computable function that is not primitive recursive: Ackermann’s function (OLP 29.14)
- Coding computations; the universal partial computable function, and why there is no universal total one (OLP 30.2-30.6)
- The halting problem, by diagonalization (OLP 29.17, 30.7)
- Computable vs computably enumerable sets (OLP 30.9-30.11)
- Reductions; Rice’s theorem (OLP 30.15, 30.20)
- Turing machines, their variants, and the Church-Turing thesis (OLP 31)
- Universal Turing machines; the Entscheidungsproblem is unsolvable (OLP 32.3-32.8)
- P and NP: verification vs solution, NP-completeness, SAT and Cook-Levin (Sipser Ch. 7)
- What it means for a problem to be hard
Slides
Session 15 Slides: Download PDF
Readings
- The Open Logic Project, Ch. 29, 30, 31, 32
- Introduction to the Theory of Computation (Sipser), Ch. 3 through 5, 7
Exercises & Extra Steps
- Practice (not collected): prove the halting problem undecidable, writing out the diagonal construction in full
- Practice (not collected): show “does this program ever print 7” is undecidable by reduction
- Practice (not collected): show 3-SAT reduces to Independent Set
- Problem Set 5 released today — due on paper at the start of S16 (Mon 9 Nov)
Navigation
- ← Previous: S14: Programming Paradigms & Functional Programming
- Back to Course Overview
- Next: S16: Catch-Up & Proof Clinic →
Questions? Reach out on the course WhatsApp!