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
• 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.; RNDr. Petr Kučera, Ph.D.
• Teacher(s): doc. RNDr. Antonín Kučera, CSc.
• 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

English

An introductory course on computability, relative computability, and arithmetical hierarchy

Last update: T_KTI (30.04.2015)

Czech

Přednáška pokrývá základy teorie algoritmů, relativní vyčíslitelnosti a aritmetické hierarchie.

Last update: T_KTI (29.04.2015)

Aim of the course

English

To learn fundamentals of computability

Last update: Hric Jan, RNDr. (07.06.2019)

Czech

Naučit základy vyčíslitelnosti

Last update: T_KTI (23.05.2008)

Course completion requirements

English

Oral examination

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

Czech

Ústní zkouška

Last update: Hric Jan, RNDr. (07.06.2019)

Literature

English

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

Last update: T_KTI (29.04.2015)

Czech

Demuth O., Kryl R., Kučera A.: Teorie algoritmů I, II. SPN, 1984, 1989

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

Last update: T_KTI (29.04.2015)

Requirements to the exam

English

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)

Czech

Zkouška sestává z ústní části. Známka ze zkoušky odpovídá hodnocení ústní části.

Požadavky u ústní zkoušky odpovídají sylabu předmětu v rozsahu, který byl prezentován na přednášce.

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

Syllabus

English

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.

Last update: T_KTI (30.04.2015)

Czech

Základy vyčíslitelnosti

• Algoritmicky vyčíslitelné funkce, numerace, s-m-n věta

• Základní vlastnosti rekurzivních a rekurzivně spočetných množin - shrnutí

• Věty o rekurzi a jejich aplikace

• Produktivní a kreativní množiny a jejich vlastnosti

• Efektivně neoddělitelné dvojice množin, Gödelovy věty o neúplnosti

Relativní vyčíslitelnost

• Relativní vyčíslitelnost, částečně rekurzivní funkcionály, Turingovská převeditelnost

• Stupně nerozhodnutelnosti, operace skoku, relativizovaný halting problém

• Limitní vyčíslitelnost

• Aritmetická hierarchie, věta o hierarchii

• Aplikace teorie vyčíslitelnosti

Last update: T_KTI (29.04.2015)

Entry requirements

English

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

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

Czech

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

Last update: T_KTI (29.04.2015)