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, 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)

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
Exercises. Example solutions.

25 Nov. Turing machines
Material: lecture notes
Exercises. Example solutions.

02 Dec. The Church-Turing thesis
Material: Chapter 3.7 of book + SEP article
Exercises: 1 and 2 on p. 71 of book. Example solutions.

Part II: introduction to computability theory

09 Dec. Coding programs as numbers.
Material: lecture notes on coding

16 Dec. Diagonalization, halting problem, s-m-n theorem.
Material: Chapter 4.2-4.4 of book.
Exercises. Example solutions.

13 Jan. Universal programs, Kleene normal form, reduction between problems.
Material: class handout. Chapter 5 except for 5.2.2, Chapter 6 up to 6.1.5.
Exercises + example solutions.

20 Jan. Rice’s theorem, partial decidability.
Material: Chapter 6.1.6-6.1.7 and 6.6.1-6.6.6
ExercisesExample solution to the second one.

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.)

Practice exam. Example solutions.


10 Feb. Final exam.
Example solutions to some exam problems