Sylabus
Prosté množiny
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. Aplikace teorie vyčíslitelnosti.
Anotace
Navazující přednáška na Vyčíslitelnost I.
Různé typy rekurzivně spočetných množin. Vztah k matematické logice. Relativní vyčíslitelnost. Operace skoku. Aritmetická hierarchie.