2-INF-264 Theory of Declarative Programming

News

Info

Here you will find the course information sheet.

Goal

Syllabus

Primitive Recursive Functions. Basic functions and operations (composition of functions and primitive recursion). Explicit definitions. Bounded minimalization. Pairing function and arithmetization. Backward recursion. Recursion with substitution in parameters. Nested simple recursion. Recursion with measure. Regular recursive definitions.

General Recursive Functions. Beyond primitive recursion: Ackermann-Péter function, universal function for primitive recursive functions. Primitive recursive indices. Transfinite recursion. General recursive functions. Regular minimalization. μ-Recursive functions.

Partial Recursive Functions. First recursion theorem (fixed point theorem). Computation model. Equivalence of the operational and denotational semantics. Partial recursive functions. Unbounded minimalization. Arithmetization of computation. Kleene normal-form theorem. Universal function. Recursive indices. Enumeration theorem. Partial μ-recursive functions. Recursively decidable, semidecidable and undecidable problems. Church thesis.

Literature

• J. Komara. Recursive Functions. Downloadable lecture notes available through the web page of the course.
• J. Komara and P. J. Voda. Lecture Notes in Theory of Computability. 2001. (PostScript) (Adobe Acrobat Document)
• J. Komara and P. J. Voda. Metamathematics of Computer Programming. 2001. (PostScript) (Adobe Acrobat Document)
• I. Korec. Úvod do teórie algoritmov. Skriptá MFF UK, 1981.

Prerequisities

Recommended:

• 1-AIN-505 Introduction to Declarative Programming
• 1-INF-465 Declarative Programming
• 1-AIN-470 Specification and Verification of Programs

Next

Semesters

• Winter 2015/16