SubjectsSubjects(version: 916)
Course, academic year 2022/2023
   Login via CAS
Recursion - NTIN073
Title: Rekurze
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2017
Semester: winter
E-Credits: 3
Hours per week, examination: winter s.:2/0, Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
Virtual mobility / capacity: no
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Guarantor: doc. RNDr. Antonín Kučera, CSc.
Class: Informatika Mgr. - Teoretická informatika
Classification: Informatics > Theoretical Computer Science
Pre-requisite : NTIN064
Is co-requisite for: NTIN074
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.
Aim of the course -
Last update: RNDr. Jan Hric (07.06.2019)

To learn fundamentals of recursion theory

Course completion requirements -
Last update: doc. RNDr. Antonín Kučera, CSc. (07.06.2019)

Oral examination

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

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.

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.
  • Low basis theorem.
  • Diagonally noncomputable functions.
  • Degrees of complete extensions of Peano arithmetic
  • Priority methods of constructions of computably enumerable sets.

Entry requirements - Czech
Last update: T_KTI (29.04.2015)

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

Charles University | Information system of Charles University |