Computability Theory

Computability theory is a branch of mathematical logic, of computer science, and of the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. In the course we focus on relative computability of computably enumerable sets.

1) Computability theory basics. The Turing machines and their numberings. The parametrization theorem. Recursion Theorem.
2) Relative computability. The oracle Turing machines. The upper semilattice of Turing degrees. Turing jumps.
3) Forcing in computability theory. Degrees between 0 and 0’. Exact pair theorem. Friedberg jump inversion.
4) Arithmetical hierarchy. Computably enumerable sets. The arithmetical hierarchy theorem.  Limit lemma. The Arslanov’s fixed point theorems.
5) The Post problem and immunity properties. Immune and simple sets. Hyperimmune and hypersimple sets. Maximal sets. The existence of complete maximal set. Hyperhyperimmunity and Boolean algebras.
6) Priority arguments. The Friedberg-Muchnik Theorem. Sacks Splitting Theorem.
7) Pi-0-1 classes. Trees and Pi-0-1 classes. Minimal degrees. Low Basis Theorem. Priority free solution of Post problem.
8) Infinite priority arguments. Strategies on a priority tree and the true path. The Sacks Density Theorem. Jump Inversion Theorem for computably enumerable sets.
 
Soare R.I. Recursively Enumerable Sets and Degrees, Springer, 1999
Rogers H. Theory of Recursive Functions and Effective Computability, MIT-Press, 1987