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
- Π01-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
semester:
Fall
prereqs:
Consent of instructor