Annotation -
| |
|
Last update: T_KTI (20.04.2004)
Advanced course on computability theory. Arithmetical hierarchy of classes of sets.
Diagonally nonrecursive functions. Arithmetical forcing.
Computably enumerable sets, priority methods.
Last update: T_KTI (20.04.2004)
Pokročilejší partie teorie rekurze. Aritmetická hierarchie tříd množin. Diagonálně nerekurzivní funkce. Aritmetický forcing. Konstrukce rekurzivně spočetných množin, prioritní metody. |
Aim of the course -
| |
|
Last update: RNDr. Jan Hric (07.06.2019)
To learn fundamentals of recursion theory
Last update: T_KTI (23.05.2008)
Naučit základy teorie rekurze
|
Course completion requirements -
| |
|
Last update: doc. RNDr. Antonín Kučera, CSc. (07.06.2019)
Oral examination
Last update: doc. RNDr. Antonín Kučera, CSc. (07.06.2019)
Ústní zkouška |
Literature -
| |
|
Last update: T_KTI (29.04.2015)
Nies. Computability and randomness, Oxford Logic Guides. Oxford University Press, Oxford, 2009.
R. Downey, D. Hirschfeldt, Algorithmic randomness and complexity, Springer, 2010
P. Odifreddi: Classical recursion theory. North-Holland, 1989
R.I. Soare: Recursively enumerable sets and degrees. Springer-Verlag, 1987
M. Li, P. Vitanyi: An introduction to Kolmogorov complexity and its applications.
Springer-Verlag, 1997
Last update: T_KTI (29.04.2015)
Demuth O., Kryl R., Kučera A.: Teorie algoritmů I,II. SPN, 1984, 1989
Nies. Computability and randomness, Oxford Logic Guides. Oxford University Press, Oxford, 2009.
R. Downey, D. Hirschfeldt, Algorithmic randomness and complexity, Springer, 2010
P. Odifreddi: Classical recursion theory. North-Holland, 1989
R.I. Soare: Recursively enumerable sets and degrees. Springer-Verlag, 1987
M. Li, P. Vitanyi: An introduction to Kolmogorov complexity and its applications.
Springer-Verlag, 1997
|
Requirements to the exam -
| |
|
Last update: doc. RNDr. Antonín Kučera, CSc. (09.10.2017)
The course is finished by an oral examination.
Requirements at the oral examination correspond to the syllabus of the subject.
Last update: doc. RNDr. Antonín Kučera, CSc. (06.10.2017)
Zkouška sestává z ústní části. Známka ze zkoušky odpovídá hodnocení ústní části.
Požadavky u ústní zkoušky odpovídají sylabu předmětu v rozsahu, který byl prezentován na přednášce. |
Syllabus -
| |
|
Last update: T_KTI (30.04.2015)
- Arithmetical forcing, 1-generic and n-generic sets and their properties.
- Arithmetical hierarchy of classes of sets.
- Classes of infinite branches of computable trees.
- Diagonally noncomputable functions.
- Degrees of complete extensions of Peano arithmetic
- Priority methods of constructions of computably enumerable sets.
Last update: T_KTI (29.04.2015)
Přednáška z teorie rekurze, která pokrývá základní typy forcingu a základní typy konstrukcí v teorii rekurze.
- Základy aritmetického forcingu, 1-generické a n-generické množiny
- Vlastnosti 1-generických množin
- Aritmetická hierarchie tříd množin
- Třídy nekonečných větví rekurzivních stromů
- Diagonálně nerekurzivní funkce
- Stupně kompletních rozšíření Peanovy aritmetiky
- Prioritní metody konstrukcí rekurzivně spočetných množin
|
Entry requirements - Czech | |
|
Last update: T_KTI (29.04.2015)
Znalosti na úrovni přednášky Vyčíslitelnost
|
|