Computability 2019

This course introduces some classical models of computation, and it covers the fundamental notions, techniques, and results of computability theory.

Times and location

Class: Wednesday, 12-14. Ludwigstr. 31, Room 021.
Exercise session: Thursday, 14-15. Ludwigstr. 28, Room 503.


Basic knowledge of first-order logic.


Final exam on 24-07


N. J. Cutland, Computability: an introduction to recursive function theory.

Course program (preliminary)

24-04 Introduction
Material: Slides, Ch. 1.1-1.3 of the book.
Exercises: 1(a,b,c,d) on pp. 21-22 + this exercise

Part I: models of computation

08-05 Unlimited register machines
Material: Ch. 1.4-1.5.
Exercises for 16-05.

15-05 Recursive functions
Material: Ch. 2 and 3.2.
Exercises for 23-05.

22-05 Turing machines
Lecture notes.

29-05 Post systems

05-06 The Church-Turing thesis, coding of programs

Part II: introduction to recursion theory

12-06 Diagonalization, halting problem, s-m-n theorem, Kleene normal form

19-06 Universal program, Reduction between problems, Rice’s theorem

26-06 Partial decidability

03-07 Recursive and recursively enumerable sets

10-07 An application: Church’s theorem

17-07 Connections with arithmetics and Gödel’s theorem

24-07 Final exam