• Definice rozhodnutelných (algoritmicky řešitelných) a nerozhodnutelných problémů
• Existence nerozhodnutelných problémů
• Nerozhodnutelnost problému univerzality
• Pojem algoritmické redukce mezi problémy
• Metoda redukce pro důkaz nerozhodnutelnosti problému

Cvičení

• konstrucke redukce
• procvičení metódy redukce
• ukázka důkazu nerozhodnutelnosti pomocí redukce

Literatura
J. Hromkovič kapitola 4
P. Jančar kapitola 6