en | de

Computability Theory

master program

VU3  WS 2023/2024  703317


The course will introduce and relate different models of computation:


week date topics slides exercises solutions
1 02.10 primitive recursion pdf (1x1, 4x1) pdf pdf
2 09.10 Gödel numbering, Ackermann function, recursive functions pdf (1x1, 4x1) pdf pdf
3 16.10 LOOP programs, elementary functions, Grzegorczyk hierarchy pdf (1x1, 4x1) pdf pdf
4 23.10 WHILE programs, (partial) recursive functions, Kleene's normal form theorem pdf (1x1, 4x1) pdf pdf
5 30.10 normal form theorem, undecidability, s-m-n theorem, fixed point theorem pdf (1x1, 4x1) pdf pdf
6 06.11 recursive (enumerable) sets, diophantine sets pdf (1x1, 4x1) pdf pdf
7 13.11 combinatory logic, Church numerals, combinatorial completeness pdf (1x1, 4x1) pdf pdf
8 20.11 Church – Rosser theorem, Z property, CL representability pdf (1x1, 4x1) pdf pdf
9 27.11 normalization theorem, CL representability pdf (1x1, 4x1) pdf
10 04.12 arithmetization, fixed point theorem, undecidability, types pdf (1x1, 4x1) pdf
11 11.12 typing, strong normalization, intuitionistic propositional logic
12 08.01 Hilbert systems, Curry – Howard isomorphism, intuitionistic propositional logic
13 15.01
14 22.01
15 29.01 test


Slides as well as solutions to selected exercises will be made available online. Accompanying literature will be linked from the course website.