Inhalt
The course will introduce and relate different models of computation:
- recursive function theory
- combinatory logic
- loop/while programs
Zeitplan
| Woche |
Datum |
Themen |
Folien |
Proseminar |
Musterlösungen |
|---|
| 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 |
|
|
|
Literatur
Slides and solutions to selected exercises will be made available online.
Accompanying literature will be provided.