The basic theory of partial -recursive operators
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.
- A lift of a theorem of Friedberg: A Banach-Mazur functional that coincides with no α-recursive functional on the class of α-recursive functions
- A Machine-Independent Theory of the Complexity of Recursive Functions
- Classes of Recursively Enumerable Sets and Their Decision Problems
- Effective operations on partial recursive functions
- scientific article; zbMATH DE number 3127536 (Why is no real title available?)
- scientific article; zbMATH DE number 3138239 (Why is no real title available?)
- scientific article; zbMATH DE number 3499732 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- Metarecursively enumerable sets and their metadegrees
- On generalized computational complexity
- Some Theorems on Classes of Recursively Enumerable Sets
- Splitting an α-Recursively Enumerable Set
- The fine structure of the constructible hierarchy
- The irregular and non-hyperregular -r.e. degrees
- The operator gap theorem in α-recursion theory
- The α-finite injury method
This page was built for publication: The basic theory of partial \(\alpha\)-recursive operators
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1078175)
