Computability Theory: Structure or Algorithms?
Jens Erik Fenstad, University of Oslo.
Abstract
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.