en | de

Computability Theory

master program

VU3  SS 2022  703317


The course will introduce and relate different models of computation:


week date topics slides exercises solutions
1 07.03 primitive recursion, Gödel numbering pdf (1x1, 4x1) pdf pdf
2 14.03 Ackermann function, recursive functions, LOOP programs pdf (1x1, 4x1) pdf pdf
3 21.03 elementary functions, Grzegorczyk hierarchy, WHILE programs pdf (1x1, 4x1) pdf pdf
4 28.03 partial recursive functions, Kleene's normal form theorem pdf (1x1, 4x1) pdf pdf
5 04.04 s-m-n theorem, fixed point theorem, r.e. sets, diophantine sets pdf (1x1, 4x1) pdf pdf
6 25.04 combinatory logic, Church numerals pdf (1x1, 4x1) pdf pdf
7 02.05 combinatorial completeness, Church – Rosser theorem pdf (1x1, 4x1) pdf pdf
8 09.05 Z property, CL representability pdf (1x1, 4x1) pdf pdf
9 16.05 normalization theorem, arithmetization pdf (1x1, 4x1) pdf pdf
10 23.05 fixed point theorem, types, strong normalization pdf (1x1, 4x1) pdf pdf
11 30.05 typing, intuitionistic propositional logic, Curry – Howard isomorphism pdf (1x1, 4x1) pdf pdf
12 13.06 diophantine sets, intuitionistic propositional logic pdf (1x1, 4x1) pdf pdf
13 20.06 test practice pdf (1x1, 4x1) pdf pdf
14 29.06 test


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