Math 773: Computability Theory

An introductory course in computablity (or recursion) theory, covering the following topics:

• Computable sets and (partial) computable functions
• The Recursion Theorem
• Computably enumerable sets; the halting problem
• Relativization; Turing reducibility (relative computability); the Turing degrees
• Turing jump
• Strong reducibilities; the arithmetical hierarchy; its relationship to the jump
• Complexity of index sets
• Low and high degrees; Martin's high domination theorem; other jump classes
• Forcing the jump; Friedberg and Shoenfield jump inversion
• Minimal pairs; exact pairs; degrees without a meet
• 1-generic, hyperimmune, and hyperimmune-free degrees
• Minimal degrees
• Immune, simple, hypersimple, cohesive, and maximal sets
• Diagonally non-computable functions; Arslanov's completeness criterion
• Π⁰₁-classes; PA degrees; the low and hyperimmune-free basis theorems
• Finite Injury; simple permitting; the Friedberg-Muchnik theorem; cone avoidance; Sacks splitting theorem
• Priority trees; infinite injury; Sacks jump inversion
• Computable well-orderings; constructive ordinals; Kleene's O
• Hyperarithmetical hierarchy; the analytical hierarchy; the Harrison linear order