Content
The course will introduce and relate different models of computation:
- recursive function theory
- combinatory logic
- loop/while programs
Schedule
| week |
date |
topics |
slides |
exercises |
solutions |
|---|
| 01 |
05.10 |
primitive recursion |
pdf (1x1, 4x1) |
pdf |
|
| 02 |
12.10 |
Gödel numbering, Ackermann function, recursive functions |
pdf (1x1, 4x1) |
pdf |
|
| 03 |
19.10 |
loop programs, elementary functions, Grzegorczyk hierarchy |
|
|
|
| 04 |
09.11 |
while programs, (partial) recursive functions, Kleene's normal form
theorem |
|
|
|
| 05 |
16.11 |
normal form theorem, undecidability, s-m-n theorem, fixed point theorem |
|
|
|
| 06 |
23.11 |
recursive (enumerable) sets, diophantine sets, Fibonacci numbers |
|
|
|
| 07 |
30.11 |
combinatory logic, Church numerals, combinatorial completeness |
|
|
|
| 08 |
07.12 |
Church – Rosser theorem, Z property, CL representability |
|
|
|
| 09 |
14.12 |
normalization theorem, CL representability |
|
|
|
| 10 |
11.01 |
arithmetization, fixed point theorem, undecidability, typing, strong
normalization |
|
|
|
| 11 |
18.01 |
intuitionistic propositional logic, Hilbert systems, Curry – Howard
isomorphism |
|
|
|
| 12 |
25.01 |
test |
|
|
|
Literature
Slides and solutions to selected exercises will be made available online.
Accompanying literature will be provided.