Introduction to Computability 2020

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)

04 Nov. Introduction
Material: slides + Chapter 1.1-1.3 of the book.
Exercises: 1(a,b) on p. 21 + these

Part I: models of computation

11 Nov. Unlimited register machines
Material: Chapter 1.4 + 2.1-1.3
Exercises. Example solutions.

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.