MATH 573
Recursive Function Theory

Credit: 4 hours.


(MATH 412) Various characterizations of the class of recursive (i.e., computable) functions; the Church-Turing thesis; unsolvability of the halting problem; the recursion theorem and the enumeration theorem; relative computability, the jump operation, and the arithmetical hierarchy; recursively enumerable sets; degrees of unsolvability; and the priority method. Prerequisite: MATH 570 or consent of instructor.