21-604 Introduction to Recursion Theory

12 units, Carnegie Mellon University

Models of computation, computable functions, solvable and unsolvable problems, reducibilities among problems, recursive and recursively enumerable sets, the recursion theorem, Posts problem and the FriedbergMuchnik theorem, general degrees and r.e. degrees, the arithmetical hierarchy, the hyperarithmetical hierarchy, the analytical hierarchy, higher type recursion. Three 50 minute lectures

Prerequisites: (21-235 (min B) or 21-355 (min B) or 21-455 (min B)) and (21-373 (min B) or 21-237 (min B))

Courseweave needs JavaScript to show sections, workloads and planning tools.