MATH 6010 - Computability Theory Course uri icon



  • Studies the computable and uncomputable. Shows that there are undecidable problems and from there builds up the theory of sets of natural numbers under Turing reducibility. Studies Turing reducibility, the arithmetical hierarchy, oracle constructions and end with the finite injury priority method. Department enforced prerequisite: MATH 6000.


  • Mayr, Peter  
    Primary Instructor - Spring 2019 / Spring 2021