MATH-6010 (3) Computability Theory

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 prereq., MATH 6000. Requisites: Restricted to graduate students only.