SubjectsSubjects(version: 845)
Course, academic year 2019/2020
   Login via CAS
Computability - NTIN064
Title in English: Vyčíslitelnost
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2015
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: 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
Is incompatible with: NTIN090
Is pre-requisite for: NTIN073
In complex interchangeability with: NTIN090
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 - Czech
Last update: T_KTI (29.04.2015)

Znalosti na úrovni přednášky Základy složitosti a vyčíslitelnosti

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html