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 
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, smn 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 



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