CISC 801: Recursive Function Theory

Catalog Description:
Advanced abstract computability (or recursive function) theory with emphasis on the tools underpinning research in the area. Topics include universal programming systems, complexity results, oracular computations and quantifier hierarchies, classification of algorithmically enumerable sets, machine self-reference and priority arguments.

Goals:
The student should learn the principal advanced concepts and mathematical tools of recursive function theory.

Contents:
The course presents advanced concepts and tools from recursive function theory, an abstract level of computability theory. Topics include the following.

• Universal Programming systems (numberings) for the partial computable functions, computable isomorphism of maximal universal programming systems, and relevance to programming languages.
• Program structure in universal programming systems.
• Recursion theorems and machine self-reflection.
• Speed-up theorems, program size and complexity tradeoff results.
• Algorithmic unsolvability results, oracular computations, and computable operators.
• Degrees of unsolvability, quantifier hierarchies, and limiting-computable procedures.
• Creative, simple, hypersimple, and maximal computably enumerable sets.
• Priority arguments.

Reference:
H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967 (Reprinted: MIT Press, 1987).

Helpful Knowledge:
Either CISC 601 or at least one course in which the student was required to prove theorems and familiarity with at least one general model of computation, for example, the Turing machine model.