FOM: parsing Soare; recursion theory's identity crisis

[Stephen G Simpson]

Roger Bishop Jones writes:

 > It seems to me clear from Soare's 95 paper that he is proposing
 > that the term "computability theory" should be used for what has
 > hitherto been called "recursion theory".  He says so in plain
 > English.

Are you absolutely certain that Soare is saying that?  I think we need
to parse him fairly carefully.  The key recommendation in his 1995
position paper reads

   Recommendation 4.  We should call the subject "*Computability
   Theory*" or simply *Computability* instead of *Recursive Function
   Theory* or *Recursion Theory*.

but he never says what "the subject" is.  Is it the same subject that
used to be called, and in some quarters still is called, recursive
function theory?  After reading Soare's paper carefully, that's not at
all clear to me; far from it.

As evidence that there is a lot of confusion here, let me recall that
Martin Davis and other computability theorists have been unable to
answer my specific question: Does computability theory include
asymptotic complexity theory, or doesn't it?  It appears that this
question is somehow embarrassing for them.  Note that Soare's "mixture
of concepts, goals, themes, and connections with other areas" includes
complexity theory, but Cholak's list of computability theorists does
not include the leading complexity theorists.

Perhaps some FOMers are wondering why I care about Soare's 1995
position paper.  After all, does it really matter?  Isn't it only a
matter of a trivial name change?  Isn't it only a matter of public
relations?

My answer is that "recursive function theory" needs to be rescued from
itself.  For at least four decades, "recursive function theory" has
suffered from a kind of split personality or identity crisis, because
its practitioners are almost exclusively concerned with the study and
classification of *non-recursive* functions and sets.  The
consequences of this terminological disconnect are aggravated by the
fact that *other people* have done a lot of unrelated but very
important research on the study and classification of *recursive*
(i.e. computable) functions and sets.  One could argue that some of
this other work rises to an extraordinarily high level of general
intellectual interest.  In any case, this other work is of a very
different character from what the "recursive function theorists" do.
Let me mention only two of these interesting lines of research: (1)
asymptotic complexity; (2) provably recursive functions.  The fact
that "recursive function theory" virtually ignores these and similar
lines of research, which are devoted to the actual study of recursive
functions, must look very peculiar to at least some outsiders.  And
Soare's proposal to change the name of the subject to "computability
theory" (if that's what he is proposing) only makes the disconnect
even worse.

As an example, consider the upcoming conference on "Computability
Theory and Applications", organized by Lempp.  From a general
scientific viewpoint, the title of the conference is very misleading,
because the conference will deal only with non-computable stuff.  The
proposed "applications" are things like "computable algebra",
"computable model theory", and reverse mathematics.  Subjects such as
complexity theory and hierarchies of recursive functions will not be
on the program.  My question is: What's going on here?  Why the
disconnect?

In my opinion, there is need for a much more detailed discussion of
the issues raised in Soare's 1995 position paper.  For starters, how
about a clear definition of "the subject" which Soare insists on
calling "Computability Theory"?

-- Steve