Syllabus
Introduction to computability
- Algorithmically computable functions, numbering, the s-m-n theorem.
- Basic properties of computable and computably enumerable sets.
- Recursion theorems and their applications.
- Productive and creative sets and their properties.
- Effectively inseparable sets, Gödel incompletness theorems.
Relative computability
- Relative computability, Turing functionals, T-reducibility.
- Degrees of undecidability, jump operation, relativized halting problem.
- Limit computability.
- Arithmetical hierarchy, basic properties. Hierarchy theorem.
- Applications of computability theory.
Annotation
An introductory course on computability, relative computability, and arithmetical hierarchy