Introduction to Recursion Theory

12 units · Graduate

Intermittent: 12 units Models of computation, computable functions, solvable and unsolvable problems, reducibilities among problems, recursive and recursively enumerable sets, the recursion theorem, Post's problem and the Friedberg-Muchnik theorem, general degrees and r.e. degrees, the arithmetical hierarchy, the hyper-arithmetical hierarchy, the analytical hierarchy, higher type recursion. (Three 50 minute lectures) Prerequisites: ( 21-355 Min. grade B or 21-235 Min. grade B or 21-455 Min. grade B) and ( 21-373 Min. grade B or 21-237 Min. grade B)