Vybudovať matematické základy deklaratívnych programovacích jazykov. Programy sú definície rekurzívnych funkcií. Dátové štruktúry sa kódujú do prirodzených čísel. Výpočtový model je založený na redukcií termov. Problémy sa riešia na cvičeniach v programovacom jazyku CL.

Primitívne rekurzívne funkcie. Základné funkcie a operácie (kompozícia funkcií, primitívna rekurzia). Explicitné definície. Ohraničená minimalizácia. Párovacia funkcia a aritmetizácia. 'Course of values recursion'. Spätná rekurzia. Substitúcia v parametri. 'Nested simple recursion'. Rekurzia s mierou. Regulárne rekurzívne definície. Klauzálny jazyk.
Obecne rekurzívne funkcie. Poza primitívnu rekurziu: Ackermann-Péterovej funkcia, univerzálna funkcia pre primitívne rekurzívne funkcie. Primitívne rekurzívne indexy. Transfinitná rekurzia. Obecne rekurzívne funkcie. Regulárna minimalizácia. μ-rekurzívne funkcie.
Čiastočne rekurzívne funkcie. Prvá veta o rekurzii (veta o pevnom bode). Výpočtový model. Ekvivalentnosť operačnej a denotačnej sémantiky. Čiastočne rekurzívne funkcie. Operátor minimalizácie. Aritmetizácia výpočtového modelu. Kleeneho veta o normálnej forme. Univerzálna funkcia, rekurzívne indexy a veta o enumerácií. Čiastočne μ-rekurzívne funkcie.

J. Komara and P. J. Voda. Lecture Notes in Theory of Computability. 2001.
J. Komara and P. J. Voda. Metamathematics of Computer Programming. 2001.