To learn fundamentals of recursion theory

Naučit základy teorie rekurze

Oral examination

Ústní zkouška

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

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

The course is finished by an oral examination.

Requirements at the oral examination correspond to the syllabus of the subject.

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.

• Arithmetical forcing, 1-generic and n-generic sets and their properties.

• Arithmetical hierarchy of classes of sets.

• Classes of infinite branches of computable trees.

• Low basis theorem.

• Diagonally noncomputable functions.

• Degrees of complete extensions of Peano arithmetic

• Priority methods of constructions of computably enumerable sets.

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ů

• Věta o nízké bázi

• Diagonálně nerekurzivní funkce

• Stupně kompletních rozšíření Peanovy aritmetiky

• Prioritní metody konstrukcí rekurzivně spočetných množin

Znalosti na úrovni přednášky Vyčíslitelnost