2-INF-121 Computability Theory

Info

Here you will find the course information sheet.

Goal

Syllabus

Inductively defined function classes. Primitive recursive functions. Pairing function. Arithmetization (Gödelization). Course of values recursion. Beyond primitive recursion: Ackermann-Péter function, universal function for primitive recursive functions. Regular minimalization. μ-Recursive functions. Derivation of primitive recursion via regular minimalization.

Special approaches to computability: Turing machines, register machines, partial μ-recursive functions. Equivalence of various computation models. Turing-Church thesis and computable functions. Kleene normal-form theorem. Universal function. Enumeration theorem. Index theorem. Effective operations on indices. S-m-n theorem. Second recursion theorem. Δ1-definability of the graphs of computable functions.

Decidable and undecidable problems. Halting problem. Reducibility. Rice theorem. Semidecidable problems and partially computable predicates. Kleene normal-form theorem. Enumeration theorem. Index theorem. Projection theorem. Recursive enumerable predicates. Rice-Shapiro theorem. Σ1-definability. Arithmetical hierarchy. Undecidable problems in other areas of mathematics. First-order logic is undecidable. Gödel's incompleteness theorem.

Literature

• 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

Prerequisities

Next

Semesters

• Winter 2007/08
• Winter 2008/09