INTRODUCTION TO THE THEORY OF RECURSIVE FUNCTIONS

Catalog description

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 4010 ).