MATH 8016 INTRODUCTION TO THE THEORY OF RECURSIVE FUNCTIONS (3 credits)
This is a proof-oriented course presenting the foundations of Recursion Theory. We present the definition and properties of the class of primitive recursive functions, study the formal models of computation, and investigate partially computable functions, universal programs. We prove Rice's Theorem, the Recursion Theorem, develop the arithmetic hierarchy, demonstrate Post's theorem. Introduction to the formal theories of computability and complexity is also given. (Cross-listed with CSCI 4010, CSCI 8016, MATH 4010).