Department of Mathematics

Van Vleck Hall, 480 Lincoln Drive, Madison, WI

Math 773: Computability Theory (Spring)

Mariya Soskova (Spring 2018):


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
Consent of instructor

UW-Madison Department of Mathematics
Van Vleck Hall
480 Lincoln Drive
Madison, Wi  53706

(608) 263-3054

Contact Us

Got a question about
accessibility, content
or structure of this website?