Here you will find the course information sheet.
Primitive Recursive Functions. Basic functions and operations (composition of functions and primitive recursion). Explicit definitions. Bounded minimalization. Pairing function and arithmetization. Backward recursion. Recursion with substitution in parameters. Nested simple recursion. Recursion with measure. Regular recursive definitions.
General Recursive Functions. Beyond primitive recursion: Ackermann-Péter function, universal function for primitive recursive functions. Primitive recursive indices. Transfinite recursion. General recursive functions. Regular minimalization. μ-Recursive functions.
Partial Recursive Functions. First recursion theorem (fixed point theorem). Computation model. Equivalence of the operational and denotational semantics. Partial recursive functions. Unbounded minimalization. Arithmetization of computation. Kleene normal-form theorem. Universal function. Recursive indices. Enumeration theorem. Partial μ-recursive functions. Recursively undecidable problems. Recursively decidable, semidecidable and undecidable problems. Church thesis.
Recommended:
* – updated within last 7 days | Last modified: 2015-09-17T15:12+0200 |