The basic theory of partial \(\alpha\)-recursive operators (Q1078175): Difference between revisions

This article is a comprehensive and detailed survey of the current state of the theory of partial \(\alpha\)-recursive operators and functionals for admissible ordinals \(\alpha\). Some of the results have appeared earlier and are represented here by a discussion rather than a complete proof. For both operators (from functions to functions) and functionals (from functions to ordinals), partial \(\alpha\)-recursiveness is defined via \(\alpha\)-enumeration reducibility. There are strong and weak notions corresponding to these forms of relative \(\alpha\)-recursiveness. The emphasis here is on those results for which significant new methods are needed to generalize theorems of the classical \((\alpha =\omega)\) case. In some cases only partial results are given and open problems stated. Sections 1-3 contain an introduction and full definitions which make the paper accessible to someone comfortable with ordinary recursion theory but mainly unfamiliar with \(\alpha\)-recursion. Sections 4-6 work through a succession of results which lead up to several generalizations of the Kreisel-Lacombe-Shoenfield theorem, which relates \(\alpha\)-recursive functionals to \(\alpha\)-effective operations (\(\alpha\)-partial recursive functions on the indices). The last section treats limit functionals and the generalization of Friedberg's theorem that there is a Banach-Mazur functional which coincides on the recursive functions with no recursive functional.