Related: Download | COMP winter 2007/08 | COMP winter 2008/09 | Slovenská verzia |
Here you will find the course information sheet.
Inductively defined function classes. Primitive recursive functions. Pairing function. Arithmetization (Gödelization). Course of values recursion. Beyond primitive recursion: Ackermann-Péter function, universal function for primitive recursive functions. Regular minimalization. μ-Recursive functions. Derivation of primitive recursion via regular minimalization.
Special approaches to computability: Turing machines, register machines, partial μ-recursive functions. Equivalence of various computation models. Turing-Church thesis and computable functions. Kleene normal-form theorem. Universal function. Enumeration theorem. Index theorem. Effective operations on indices. S-m-n theorem. Second recursion theorem. Δ1-definability of the graphs of computable functions.
Decidable and undecidable problems. Halting problem. Reducibility. Rice theorem. Semidecidable problems and partially computable predicates. Kleene normal-form theorem. Enumeration theorem. Index theorem. Projection theorem. Recursive enumerable predicates. Rice-Shapiro theorem. Σ1-definability. Arithmetical hierarchy. Undecidable problems in other areas of mathematics. First-order logic is undecidable. Gödel's incompleteness theorem.
* – updated within last 7 days | Last modified: 2011-08-31T20:14+0200 |