SubjectsSubjects(version: 920)
Course, academic year 2022/2023
   Login via CAS
Computability - NTIN064
Title: Vyčíslitelnost
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2022
Semester: summer
E-Credits: 3
Hours per week, examination: summer 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.
RNDr. Petr Kučera, Ph.D.
Class: Informatika Mgr. - Teoretická informatika
Informatika Mgr. - Diskrétní modely a algoritmy
Classification: Informatics > Theoretical Computer Science
Pre-requisite : NTIN090
Is co-requisite for: NTIN065
Is incompatible with: NTIX090
Is pre-requisite for: NTIN073
In complex interchangeability with: NTIN090, NTIX090
Annotation -
Last update: T_KTI (30.04.2015)
An introductory course on computability, relative computability, and arithmetical hierarchy
Aim of the course -
Last update: RNDr. Jan Hric (07.06.2019)

To learn fundamentals of computability

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)

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

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

S.B. Cooper. Computability Theory Chapman Hall, 2003

Nies. Computability and randomness, Oxford Logic Guides. Oxford University Press, Oxford, 2009

R. Downey, D. Hirschfeldt. Algorithmic randomness and complexity. Theory and Applications of Computability. Springer, New York, 2010

A. Shen, N. Vereshchagin. Computable functions, Student Mathematical Library, vol. 19, AMS, 2003

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)

Introduction to computability

  • Algorithmically computable functions, numbering, the s-m-n theorem.
  • Basic properties of computable and computably enumerable sets.
  • Recursion theorems and their applications.
  • Productive and creative sets and their properties.
  • Effectively inseparable sets, Gödel incompletness theorems.

Relative computability

  • Relative computability, Turing functionals, T-reducibility.
  • Degrees of undecidability, jump operation, relativized halting problem.
  • Limit computability.
  • Arithmetical hierarchy, basic properties. Hierarchy theorem.
  • Applications of computability theory.

Entry requirements -
Last update: doc. RNDr. Antonín Kučera, CSc. (14.02.2022)

A basic knowledge of computability equivalent to course NTIN090 (or NTIX090)

Charles University | Information system of Charles University |