FOM: Concepts of Recursion Theory

[Joseph Shoenfield]

     In some recent communications, Steve has lamented that recursion
theory has gone astray.   He says that in the beginning, computability was
the central concept of the subject, but that most of the work being done
nowadays has little or notinhg to do with computability.   I think this
statement is correct, but I do not think this means that we have gone
astray.   As recursion theory progresses, researchers discover new
concepts which are relevant to their investigations.   If they are able to
prove interesting and significant theorems about these concepts, these
concepts may become central concepts of the theory.   I would like to
illustrate this with a couple of examples.
     There is no doubt that in the early years computability was THE
central concept of recursion theory.   This was not surprising; Church's
Thesis shows that any result about recursive functions or relations is in
soie sense a result about computability.   The situation changed in the
fifties with the introduction and study of the hierarchies by Kleene and
his students.   This was a natural continuation of Kleene's earlier work,
since the relations in the hierarchies were obtained from recursive
relation by prefixing quantifiers of types 0 and 1.  However (as Kleene
noted), the class of recursive relations could be replaced here by any
of a number of smaller classes (e.g., the primitive recursive relations),
and these classes had litlle to do with computability.
     What, then, was the central concept of the study of the hierarchies?
A relation is in a certain position in the hierarchies if it can be
defined in a particular way.   This suggests that definability is the
central concept.   Of course, the definability used in the hierarchies is
of a very special kind; so it is natural to investigate if other kinds of
definability are subject to the techniques of recursion theory.   Perhaps
surprisingly, the answer is often yes.   For example, Godel's notion of
constructibility is clearly a kind of definability.  It was originally
considered as a concept in set theory, since this is where the initial
applications were made.   But later work of Jensen derived many new
application by a study of the constructible hierarchy using techniques
from recursion theory.
     This suggest some vague but interesting problems.   Is there a notion
of definability independent of the language in which the definition is
given?   At first this seems improbable; but remember that there is a
notion of computability which is independent of the method of computation,
and that the predicate calculus can be thought of as giving a notion of
proof which is independent of the axioms used in the proof.   If there is
such a notion, can techniques of recursion theory be profitably used to
prove theorems about the notion?   If the answer to these questions is
yes, we could certainly say that definability is a central notion of
recursion theory.
     Let us turn to another concept, that of a recursion.   As we have
observed, recursions were not of central importance in recursion theory in
the period in which the subject was named; but the situation has changed a
great deal since then.
     A recursion (in present day terminology) is a definition of the form
F(x)=K(F,x) where x varies through a set X; F is the partial function on X
being defined; and K is a partial functional with the indicated arguments.
The recursion provides an algorithm for computing F(x).   We try to
compute K(F,x); if this requires computing F(y), we stop are try to
compute K(F,y); and so on.   The procedure may end with the computation of
F(x); if not, F(x) is undefined.   The most important examples are
definitions by induction.   A technical point: in defining relations by
induction, we identify the relation with its semicharacteristic function,
which is 0 where the relation is true and undefined elsewhere.   The
characteristic function does not work so well here.
     Recursions enter into basic recursion theory via the Recursion
Theorem, which says that if K is recursive in a suitable sense, then F is
recursive.   (This is the First Recursion Theorem.   The theorem usually
given in texts on recursion theory is the Second Recursion Theorem, which
is similar but different in some respects.)   The Recursion Theorem has
many uses in Recursion Theory; in particular, it is a valuable tool for
showing that certain functions are recursive.
   The general theory of recursions entered Recursion Theory in a
ground-breaking paper by Spector in the book Infinitistic Methods.   His
idea was to assume that K has some position in one of the hierarchies and
then find the position of F.   He also computed an ordinal which measures
the complexity of the algorithm described above.   His work was continued
by many researchers; there is a survey by Gandy in the book Generalzed
Recursion Theory.
     The full importance of recursions in Recursion Theory only became
apparent with the introduction by Kleene of recursive function of higher
type objects.   Kleene found that the best way to define these was to
define the enumerating function.   The natural definition of this function
was is a complicated recursion, whose study is a key tool in the resulting
theory.   For example, RE relations are no longer sigma-0-1; classifying
them in the hierarchies requires a detailed examination of the algorithm
for computing the enumerating function.   Later Gandy was able to extend
the selection theorems of the classical theory by studying the ordinals
associated with this algorithm.   His methods were extended and used by
later researchers, especially Moschovakis.   Meanwhile, Kleene extended
the (First) Recursion Theorem to this theory, and observed that one could
convert the Recursion Theorem into another definition of the recursive
functions.   This again was extended by others, and Moschovakis developed
a general notion of a recursion theory based on recursions.   An
introduction to all this is the Kechris-Moschovakis paper in the Handbook
of Mathematical Logic; see also the article by Aczel in the same volume.
     I would like to draw a moral for fommers from this story.   There is
no point in criticizing researchers in mathematics for not paying enough
attention to the foundations of their subject.   If the mathematics which
they produce is good enough, the foundations of their subject will
be expanded to justify their work.