Content
The course will introduce and relate different models of computation:
- recursive function theory
- combinatory logic
- LOOP/WHILE programs
- lambda calculus
Schedule
| week |
date |
topics |
slides |
exercises |
solutions |
|---|
| 1 |
07.03 |
primitive recursion, Gödel numbering |
|
|
|
| 2 |
14.03 |
Ackermann function, recursive functions, LOOP programs |
|
|
|
| 3 |
21.03 |
elementary functions, Grzegorczyk hierarchy, WHILE programs |
|
|
|
| 4 |
28.03 |
partial recursive functions, Kleene's normal form theorem |
|
|
|
| 5 |
04.04 |
s-m-n theorem, fixed point theorem, r.e. sets, diophantine sets |
|
|
|
| 6 |
25.04 |
combinatory logic, Church numerals |
|
|
|
| 7 |
02.05 |
combinatorial completeness, Church – Rosser theorem |
|
|
|
| 8 |
09.05 |
Z property, CL representability |
|
|
|
| 9 |
16.05 |
normalization theorem, arithmetization |
|
|
|
| 10 |
23.05 |
fixed point theorem, types, strong normalization |
|
|
|
| 11 |
30.05 |
typing, intuitionistic propositional logic,
Curry – Howard isomorphism |
|
|
|
| 12 |
13.06 |
diophantine sets, intuitionistic propositional logic |
|
|
|
| 13 |
20.06 |
test practice |
|
|
|
| 14 |
29.06 |
test |
|
|
|
Literature
Slides as well as solutions to selected exercises will be made available
online. Accompanying literature will be linked from the course website.