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

Literatura:

J. Hromkovič kapitola 4

Cvičení:

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