Math 773: Computability Theory
Prerequisites:
Consent of instructor
Instructor:
Selwyn Ng
Time and Place:
MWF 1:20-2:10
textbooks:
R. I. Soare: Recursively enumerable sets and degrees (preprint available in class)
Course Content:
Turing degree and jump, strong reducibilities, arithmetic hierarchy, index sets, simple and (hyper)hypersimple sets, easy forcing arguments in computability theory, finite and infinite injury, Friedberg-Muchnik and Sacks Splitting Theorem, Sacks Jump and Sacks Density Theorems, the miminal pair method, high and low sets, $Pi^0_1$ classes, computable ordinals.