Vypočítateľnosť
(sylaby štátnic magisterského štúdia informatiky)
- Funkcie a čiastočné funkcie; projekcie, skladanie funkcií, trojice
číslovacích (párovacích) funkcií.
- Univerzálne funkcie a čiastočné funkcie.
- Primitívne rekurzívne, rekurzívne funkcie a čiastočne rekurzívne
(vypočítateľné) funkcie (na množine N).
- Primitívne rekurzívne, rekurzívne a rekurzívne spočítateľné množiny a
predikáty a ich vlastnosti.
- Modely vypočítateľnosti (Turingove stroje a iné modely).
- Ekvivalentnosť modelov vypočítateľnosti.
- Churchova téza.
- Problém zastavenia a iné nerozhodnuteľné problémy.
- Kódovanie nečíselných oborov (oborov slov) do prirodzených čísel.