ABSTRACT
In the paper Turing's “oracle”: From absolute to relative computability - and back S. Feferman discusses some major trends in recent work on degrees of un solvability, theories of recursive functionals and generalized recursion theory and notes how “marching in under the banner of degree theory, these strands were to some extent woven together by the recursion theorists, but the trend has been to pull the subject of effective computability even farther away from questions of actual computation.” (Feferman [1992a])
Feferman had expressed similar concerns in a paper from 1977 Inductive schemata and recursively continuous functionals (Feferman [1977]), and both he and Y. Moschovakis have since pursued a program of how to use “abstract re cursion theory as a foundation for a theory of algorithms” (to quote the title of a paper by Moschovakis from 1984). Some key references in the development of this program are Feferman [1991], [1992b], [1996], and Moschovakis [1984], [1989], [1997]. We particularily recommend Feferman [1992b] A new approach to abstract data types, I, Informal development, for a clear conceptual presentation of the issues involved.
