Předmět je zaměřen na hlubší studium výsledků teorie vyčíslitelnosti s důrazem na osvojení si používaných důkazových metod a technik. Cílem předmětu je: seznámit se se základními výsledky o vyčíslitelnosti nad nespočetnými množinami; získat další poznatky o klasifikaci problémů, zejména aritmetické hierarchii; seznámit se s relativizovanou teorií vyčíslitelnosti.

Osnova

• Kreativní a produktivní množiny, m-úplné množiny a 1-úplné množiny, efektivně neoddělitelné množiny, jednoduché a imunní množiny.
• Věta o rekurzi, aplikace v logice.
• Primitivně rekurzívní, totálně rekurzívní a částečně rekurzívní funkce a predikáty, ekvivalence s třídou vyčíslitelných funkcí.
• Aritmetické množiny a funkce, Goedelova-Rosserova věta o neúplnosti, druhá Goedelova věta o neúplnosti.
• Relativizovaná teorie vyčíslitelnosti. Programy s orakulem.
• Kleeneho hierarchie. T-redukce, aritmetická hierarchie, tt-redukovatelnost. Postův problém.
• Analytická hierarchie.
• Vyčíslitelnost nespočetných množin. Úplné částečně uspořádané množiny, domény.

Požadavky na absolvování předmětu

Předmět je zakončen písemnou zkouškou. Použití literatury a poznámek není při písemce povoleno.

Doporučená literatura

• Rogers, Hartley. Theory of Recursive Functions and Effective Computability. Cambridge, Massachusetts Institute of Technology, 1987.
• Texty k přednáškám (Materiály jsou dostupné pouze z domény .muni.cz)