Computability - NTIN014

• Title: Vyčíslitelnost
• Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2003
• Semester: winter
• E-Credits: 9
• Hours per week, examination: winter s.:2/1, C [HT]; summer s.:2/1, C+Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: cancelled
• Language: Czech
• Teaching methods: full-time
• Teaching methods: full-time
• Guarantor: doc. RNDr. Antonín Kučera, CSc.
• Classification: Informatics > Theoretical Computer Science
• Is co-requisite for: NTIN012
• Is incompatible with: NLTM020

Annotation

English

Last update: G_I (05.06.2002)

Turing machines. Computable functions. Primitive recursive functions. Universal function. Normal form theorem (Kleene), s-m-n theorem. Computable and computably enumerable sets. Post´s theorem. Halting problem. Recursion theorem and its applications, Rice´s theorem. Various characterizations of computable and computably enumerable sets. Productive and creative sets. Simple sets. Reducibilities (1-, m-). Complete sets. Pairs of sets. Effectively inseparable sets, Gödel incompletness theorem. Relative computability, T-reducibility. Jump operation. Limit computability. Arithmetical hierarchy.

Czech

Last update: G_I (05.06.2002)

Základní přednáška z teorie algoritmů a efektivní vyčíslitelnosti. Turingovy stroje. Částečně rekurzivní funkce. Rekurzivní a rekurzivně spočetné množiny. Algoritmicky nerozhodnutelné problémy. Věta o rekurzi. Vztah k matematické logice. Relativní vyčíslitelnost a aritmetická hierarchie.

Literature

Last update: RNDr. Pavel Zakouřil, Ph.D. (05.08.2002)

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

Syllabus

Last update: ()

Turingovy stroje, částečně rekurzivní funkce (resp. další matematická upřesnění intuitivního pojmu algoritmu), myšlenka důkazu jejich ekvivalence.

Primitivně rekurzivní funkce.

Pojem univerzální funkce, Kleeneho věta o normální formě a její význam. s-m-n věta.

Rekurzivní a rekurzivně spočetné množiny. Základní vlastnosti. Postova věta. Problém zastavení Turingova stroje a další algoritmicky nerozhodnutelné problémy.

Věta o rekurzi a její aplikace. Riceova věta.

Různé charakterizace rekurzivně spočetných a rekurzivních množin. Věty o jejich generování.

Produktivní a kreativní množiny. Prosté množiny.

• převeditelnost a m-převeditelnost. 1-úplné a m-úplné množiny.

Dvojice množin, efektivní neoddělitelnost dvojic množin a Gödelovy věty o neúplnosti.

Relativní vyčíslitelnost, T-převeditelnost.

Operace skoku, její význam jako relativizovaného halting problému a její základní vlastnosti.

Věta o limitní vyčíslitelnosti.

Aritmetická hierarchie. Věta o hierarchii, souvislost s operací skoku.