Graduate Students
Graduate Programs     
Graduate Home Ph D Programs Masters Degree Ph D Program Requirements Course Descriptions Current Courses Admissions Current Graduate Students Graduate Student Seminar SIAM Chapter Seminar Recent Graduates Incoming Students

Apply Now
Graduate Courses

21-604
Introduction to Recursion Theory

Spring: 12 units

Syllabus covers: 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 theorm, general degrees and r.e. degrees, the arithmetical hierarchy, the hyperarithmetical hierarchy,the analytical hierarchy, higher type recursion. Prerequiste: 21-300 or its equivalent.