This course introduces some classical models of computation, and it covers the fundamental notions, techniques, and results of computability theory.
Time and location
Class: Wednesday, 10-12 (c.t.), start on 02.11.
Exercise session: Wednesday 9-10 (c.t.), start on 09.11.
Classes take place via Zoom. Meeting details will be provided via LSF or email. If you have not received them by Thursday 29.10 please get in touch with me.
Basic knowledge of first-order logic.
Final exam: 10 Feb 2021, 9:30-12.
Re-sit exam: 03 Mar 2021, 9:30-12.
Details will be discussed in class.
Cutland, Computability: an introduction to recursive function theory.
Course program (preliminary)
Part I: models of computation
Part II: introduction to computability theory
27 Jan. Recursive and recursively enumerable sets
Material: Chapter 6.6.11-6.6.13. Chapter 7 up to 7.2.9.
03 Feb. Connections with arithmetic and Gödel’s theorem
Material: Chapter 7.2.13-7.2.16. Chapter 8. Class slides.
(Note: arithmetic will not be covered in the final exam.)
10 Feb. Final exam.
Example solutions to some exam problems