Adjointness in recursion (Q581396)

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.