IA046 Vyčíslitelnost
Sylabus:
- 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.
Rozvrh:
Čtvrtek, 14:00 - 15:50, B411
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.
Literatura a studijní materiály:
- Rogers, Hartley. Theory of Recursive Functions and Effective
Computability. Cambridge : Massachusetts Institute of Technology, 1987.
Konzultační hodiny:
Pondělí od 9:00 do 10:00
Čtvrtek od 9:00 do 10:00