Vyčíslitelnost - NTIN014

• Anglický název: Computability
• Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2003
• Semestr: zimní
• E-Kredity: 9
• Rozsah, examinace: zimní s.:2/1, Z [HT]; letní s.:2/1, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: zrušen
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Garant: doc. RNDr. Antonín Kučera, CSc.
• Kategorizace předmětu: Informatika > Teoretická informatika
• Je korekvizitou pro: NTIN012
• Je neslučitelnost pro: NLTM020

Anotace

čeština

Poslední úprava: 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.

angličtina

Poslední úprava: 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.

Literatura

Poslední úprava: 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

Sylabus

Poslední úprava: ()

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.