Location: Courses | CL Homepage | Dept. of Appl. Inf. (AI and DP) | Faculty of Math., Physics, and Inf. | Comenius Univ. Bratislava | Slovakia

2-INF-121 Computability Theory

Info

Here you will find the course information sheet.

Goal

To formalize notions of algorithmical solvability of problems and computability of functions, to give applications of these formalisms in computer science, logic and mathematics.

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

Prerequisities

Next

Semesters


* – updated within last 7 days Last modified: 2011-08-31T20:14+0200