Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

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
4EU+:	no
Virtual mobility / capacity:	no
State of the course:	taught
Language:	Czech, English
Teaching methods:	full-time

Guarantor:	doc. RNDr. Antonín Kučera, CSc.
Teacher(s):	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
Is pre-requisite for:	NTIN088

Opinion survey results Examination dates WS schedule Noticeboard

Annotation -

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)

Aim of the course -

To learn fundamentals of recursion theory

Last update: Hric Jan, RNDr. (07.06.2019)

Course completion requirements -

Oral examination

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

Literature -

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)

Requirements to the exam -

The course is finished by an oral examination.

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

Last update: Kučera Antonín, doc. RNDr., CSc. (09.10.2017)

Syllabus -

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.

Last update: T_KTI (30.04.2015)

Entry requirements - Czech

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

Last update: T_KTI (29.04.2015)