Recursion - NTIN073

• Title: Rekurze
• Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2015 to 2016
• Semester: winter
• E-Credits: 3
• Hours per week, examination: winter s.:2/0, Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: taught
• Language: Czech, English
• Teaching methods: full-time
• Teaching methods: full-time
• Guarantor: doc. RNDr. Antonín Kučera, CSc.
• Class: Informatika Mgr. - Teoretická informatika
• Classification: Informatics > Theoretical Computer Science
• Pre-requisite : NTIN065
• Is co-requisite for: NTIN074

Annotation

English

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.

Czech

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: T_KTI (23.05.2008)

Naučit základy teorie rekurze

Literature

English

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

Czech

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

Syllabus

English

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.

• Low basis theorem.

• Diagonally noncomputable functions.

• Degrees of complete extensions of Peano arithmetic

• Priority methods of constructions of computably enumerable sets.

Czech

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ů

• 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

Entry requirements

Last update: T_KTI (29.04.2015)

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