Adjointness in recursion
In this paper the role of adjointness in understanding properties of computable functionals is described. The author begins by providing a new characterization of the completion functor into complete \(f_ 0\) spaces (defined by Yu. Ershov). The category of complete \(f_ 0\) spaces is shown to be a reflective subcategory of the category of \(f_ 0\) spaces with reflection just soberfication with the Scott topology. Turning to the computable case, the author utilizes the environment of a topos (the recursive topos) to prove analogous results. Constructive completion (in the sense of Ershov) is shown to be a reflection, thought of as recursively enumrable soberfication, into the category of constructively complete \(f_ 0\) spaces. The presence of the adjunction provides a common framework for the analysis of different functionals. The defining property of these functionals is recursive naturality which is seen to coincide on constructively complete \(f_ 0\) spaces with the classical notions of recursivity or effectivity. Among its applications, the adjunction provides a common generalization of classical theorems such as those of Rice-Shapiro, Myhill-Shepherdson and Kreisel-Lacombe- Schoenfield.
- Generalized Banach-Mazur functionals in the topos of recursive sets
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- scientific article; zbMATH DE number 3346618 (Why is no real title available?)
- Noncomputability in analysis and physics: A complete determination of the class of noncomputable linear operators
This page was built for publication: Adjointness in recursion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q581396)
