Sylabus
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
Anotace
Přednáška pokrývá základy teorie algoritmů, relativní vyčíslitelnosti a aritmetické hierarchie.