FOM: Concepts of Recursion Theory (reply to Shoenfield)

[Stephen G Simpson]

To: Joseph Shoenfield

Joe, I really like your comments about the introduction of a lot of
interesting new concepts into recursion theory: hierarchies,
Jensen-style master codes, various kinds of recursions, etc.  We have
certainly come a long way from the days when the subject revolved
around the concept of computability, and I think this is all to the
good.

Joseph Shoenfield writes:
 > In some recent communications, Steve has lamented that recursion
 > theory has gone astray.

I don't think I ever said anything exactly along the lines of
"recursion theory has gone astray".  It's true that I'm unhappy with a
certain aspect of how recursion theory has evolved; see below.

 > 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.

This isn't the trend that I'm unhappy about.  What I'm unhappy about
is that recursion theory has largely lost touch with its f.o.m. roots.
This has had many bad effects; see Harvey's "profound changes" posting
of 12 Aug 1998 02:24:08.

As for the point that current recursion theory has little or nothing
to do with actual computing: yes, I did say something like this.  This
statement is certainly correct from *my* point of view, because I take
"recursion theory" to mean degrees of unsolvability and r.e. sets.

 > I think this statement is correct,

Do you?  In your posting of 24 Aug 1998 20:48:41, you said that
recursion theory includes complexity theory.  And I think you would
agree that complexity theory is an active subject and has a lot to do
with actual computing.  So from *your* point of view, the statement
seems *not* to be correct.  Once again the issue of where to put
complexity theory rears its head.

 > but I don't think this means that we have gone astray.

I agree; it *doesn't* mean we have gone astray; far from it.  In fact,
from the viewpoint of applications to f.o.m., I *love* non-computable
things.  I'm *extremely* fond of Turing degrees and the arithmetical
and hyperarithmetical hierarchies.  I refer to them frequently in my
forthcoming book on subsystems of 2nd order arithmetic and reverse
mathematics.  Basic information about them is tremendously useful in
f.o.m.  Indeed, I always loudly praise your book "Mathematical Logic"
for being the only introductory textbook to present the basic facts of
hyperarithmetical theory.

By the way Joe, are there any plans to reprint "Mathematical Logic"?
Many times I have wished it were available as, say, a Dover paperback.

On the issue of my lamenting the trend away from actual computation,
perhaps I was misunderstood because I didn't make myself clear.  I was
referring only to the name of the subject.  What I was trying to say
was that, in my opinion, "computability theory" is a bad name for a
subject like degrees of unsolvability and r.e. sets, which deals
exclusively with non-computable sets and functions.  In that sense,
Soare has led many people astray.  A more appropriate name might be
"non-computability theory", as Harvey proposed.  But this too has
obvious disadvantages.  I think the most accurate name is "degrees of
unsolvability and r.e. sets".  I think I'll stick to that name from
now on, to avoid confusion.

-- Steve