|Related: Download | LCS winter 2006/07 | LCS winter 2007/08 | LCS winter 2008/09 | LCS winter 2009/10 | LCS winter 2010/11 | LCS winter 2011/12 | LCS winter 2012/13 | LCS winter 2013/14 | LCS winter 2014/15||Slovenská verzia|
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 decidable, semidecidable and undecidable problems. Church thesis.
|* – updated within last 7 days||Last modified: 2015-09-17T15:13+0200|