2-INF-121 Teória vypočítateľnosti

O kurze

Poznámka: spôsob hodnotenia a ukončenia štúdia predmetu je 40/60.

Cieľ predmetu

Hlavným cieľom predmetu je formalizovať pojmy algoritmickej riešiteľnosti problémov a vypočítateľnosti funkcií a uviesť aplikácie takýchto formalizmov v informatike, logike a matematike.

Stručná osnova predmetu

Induktívne definované triedy funkcií. Primitívne rekurzívne funkcie. Párovacia funkcia. Aritmetizácia (Gödelizácia). 'Course of values recursion'. Poza primitívnu rekurziu: Ackermann-Péterovej funkcia, univerzálna funkcia pre primitívne rekurzívne funkcie. Regulárna minimalizácia. μ-Rekurzívne funkcie. Vyjadrenie primitívnej rekurzie pomocou regulárnej minimalizácie.

Špeciálne druhy algoritmickej vypočítateľnosti: Turingove stroje, registrové stroje, čiastočne μ-rekurzívne funkcie. Ekvivalentnosť vypočítateľnosti na jednotlivých modeloch. Turing-Churchova téza a vypočítateľné funkcie. Kleeneho veta o normálnej forme. Univerzálna funkcia. Veta o enumerácií. Veta o indexe. Efektívne operácie na indexoch. S-m-n veta. Druhá veta o rekurzii. Δ1-definovateľnosť grafov vypočítateľných funkcií.

Rozhodnuteľné a nerozhodnuteľné problémy. Problém zastavenia. Redukcie. Riceova veta. Polorozhodnuteľné problémy a čiastočne vypočítateľné predikáty. Kleeneho veta o normálnej forme. Veta o enumerácií a indexe. Veta o projekcii. Rekurzívna spočítateľnosť. Rice-Shapirova veta. Σ1-definovateľnosť. Aritmetická hierarchia. Nerozhodnuteľné problémy v iných oblastiach matematiky. Nerozhodnutelnosť predikátového počtu. Gödelova veta o neúplnosti.

Literatúra

J. Komara and P. J. Voda. Lecture Notes in Theory of Computability. 2001. (PostScript) (Adobe Acrobat Document)
P. J. Voda. Theory of Recursive Functions & Computability. 2000. (PostScript)
I. Korec. Úvod do teórie algoritmov. Skriptá MFF UK, 1981

Podmieňujúce predmety

Nadväzujúce predmety

Výučba

* – aktualizované v priebehu posledných 7 dní

Posledná zmena: 2011-08-31T20:14+0200