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, 10-12.
Details will be discussed in class.
Cutland, Computability: an introduction to recursive function theory.
Course program (preliminary)
Part I: models of computation
18 Nov. Recursive functions
Material: Chapter 2 and 3.2
25 Nov. Turing machines
02 Dec. Post systems
09 Dec. The Church-Turing thesis, coding of programs
Part II: introduction to computability theory
16 Dec. Coding, diagonalization, halting problem.
23 Dec. s-m-n theorem, universal programs.
13 Jan. Kleene normal form, reduction between problems, Rice’s theorem
20 Jan. Partial decidability.
27 Jan. Recursive and recursively enumerable sets
03 Feb. Connections with arithmetic and Gödel’s theorem
10 Feb. Final exam.