CSCI 4010 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 MATH 4010, MATH 8016, CSCI 8016).
Prerequisite(s): MATH 2230 or MATH 2030 with a C- or better or CSCI 3660 with a C- or better or instructor's permission.