Computability Theory: Structure or Algorithms?

Jens Erik Fenstad, University of Oslo.


In his paper "Turing's "oracle": From absolute to relative computability - and back" S.Feferman discusses some major trends in recent work on degrees of unsolvability, theories of recursive functionals and generalized recursion theory and notes how "marching in under the banner of degree theory, these stands 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 had expressed similar concerns in a paper from 1977 "Inductive schemata and recursively continous functionals", and both he and Y.Moschovakis have sice pursued a programme of how to use "abstract recursion as a foundation for the theory of algorithms" (to quote the title of a paper of Moschovakis from 1984). I had commented on this development in the introductory part of "General Recursion Theory" from 1980, and I shall in this lecture start from this point, briefly reviewing some developments at that time in axiomatic recursion theory (computation theories) and fap-computability, paying particular attention to both structural and algorithmic concerns. The main part of my lecture will be devoted to current developments in computability theories on many-sorted algebras, which generalises earlier work on fap-computability; see the forthcoming survey by J.V.Tucker and J.I.Zucker "Computable functions and semicomputable sets on many-sorted algebras" (to appear in vol.5 of The Handbook of Logic in Computer Science). I will indicate how this approach unifies a number of developments in "real" computability, in particular, how it relates to the recent work of S.Smale (see the book by Blum, Cucker, Shub and Smale, 1998) on computation and complexity over the reals. I will conclude with some remarks on computability over the non-standard reals.