M-INBP-004 Teória vypočítateľnosti pre programátorov

O kurze

Cieľ predmetu

Úvod do teórie rekurzívnych funkcií a teórie vypočítateľnosti. Ukážeme, že rekurzívne funkcie sú matematickým základom pre teóriu deklaratívnych programovacích jazykov. Teoretické témy prednášok sú prakticky precvičené za počítačom.

Stručná osnova predmetu

Induktívne definované triedy funkcií. Explicitne a rekurzívne definície funkcií a predikátov. Primitívne rekurzívne funkcie. Rekurzívne funkcie a ich efektívny výpočet. Kleeneho vety o normálnej forme a o rekurzii. μ-rekurzívne funkcie. Turingove stroje. Ekvivalentnosť Turingových strojov a rekurzívnosti. Turing-Churchova téza a vypočitateľné funkcie.

Rozhodnuteľné a nerozhodnuteľné problémy. Polorozhodnuteľné problémy. Aritmetická hierarchia. Nerozhodnuteľné problémy v iných oblastiach matematiky. Nerozhodnutelnosť predikátového počtu. Goedelova 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

Výučba

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

Posledná zmena: 2008-09-17T17:47+0200