SubjectsSubjects(version: 845)
Course, academic year 2019/2020
   Login via CAS
Computability II - NTIN065
Title in English: Vyčíslitelnost II
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2015 to 2019
Semester: summer
E-Credits: 3
Hours per week, examination: summer s.:2/0 Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: not taught
Language: Czech
Teaching methods: full-time
Guarantor: doc. RNDr. Antonín Kučera, CSc.
Class: Informatika Mgr. - Teoretická informatika
Informatika Mgr. - Diskrétní modely a algoritmy
Classification: Informatics > Theoretical Computer Science
Co-requisite : NTIN064
Annotation -
Last update: T_KTI (20.04.2004)
A continuation of Computability I. Various types of computably enumerable sets. A connection to mathematical logic. Relative computability. Jump operation. Arithmetical hierarchy.
Aim of the course - Czech
Last update: T_KTI (23.05.2008)

Naučit další navazující teorii vyčíslitelnosti

Literature -
Last update: T_KTI (29.04.2015)

Soare R. I.: Recursively enumerable sets and degrees. Springer-Verlag, 1987

Odifreddi P.: Classical recursion theory. North-Holland, 1989

Syllabus -
Last update: T_KTI (20.04.2004)

Simple sets.

Relative computability, T-reducibility.

Jump operation, basic properties. Limit computability.

Arithmetical hierarchy, basic properties. Applications of the theory of computability.

Charles University | Information system of Charles University |