FOM: Recursion Theory and Computability Theory

[Joe Shipman]

It appears that Simpson's call for examples of applications of priority
arguments and other recursion-theoretic methods outside of recursion
theory has been adequately met by Fenner and Kurtz, especially in the
area of computational complexity.  This tends to justify Soare's
proposal to use the term "computability theory" to include both
"recursion theory" and "computational complexity", since these subjects
started together and used the same methods before developing in
different directions about thirty years ago.  (I am not sure exactly
what "theory of computation" connotes that is distinct from
"computational complexity theory" but it would also be subsumed.)   But
I hope Soare is aware that such a terminological shift may further
marginalize the work that recursion theorists do on higher degrees --
the Slaman-Woodin result on rigidity of degrees above 0'' is a beautiful
theorem but it is hard to say it is really related to computation.

I have no problem classifying any work about the degrees reducible to 0'
as "computability theory"; partial recursive functions come from Turing
machines and Turing machines are computers.  I'd even be willing to
include a result about 0'', since the set of Turing machines that
compute total functions is obviously related to computability.  But any
work in "recursion theory" which is about higher sets than this can be
about *definability* but *not* about *computability*.

It is most unfortunate when the broad subject classifications that have
become useful (e.g. the division of logic into model, proof, set, and
computability theories) have the effect of marginalizing and orphaning
good work that doesn't fit the classification because it falls between
or across the categories.  I'd like to see people contribute further
examples of this phenomenon here.

That it seems to be the *methods* rather than the *results* of classical
recursion theory which have found application is significant.  I am not
persuaded yet that the Sacks Density Theorem is really used in an
interesting way in the papers in geometry that Soare cites; perhaps when
that work is more thoroughly reviewed and published someone will be
better able to clarify this for us on the FOM forum.   This is related
to the lack of "natural examples" of intermediate c.e. degrees; I think
Soare failed to adequately answer this criticism.  Conjecture: there ARE
natural examples.  I'd like to see Soare, Simpson, or Friedman or some
other expert give some good intuitive reasons for believing or
disbelieving this (imprecisely stated) conjecture, rather than spending
a lot of time on the minutiae of who said what to whom when about which
results, or on issues related to the tone rather than the substance of
postings.

I agree with Odifreddi's remarks

>it is perfectly justified, in my view, to use all the machinery one can

>use to prove the definability of the jump or the existence of
nontrivial
>automorphisms of the degrees. perhaps it is less to use monster injury
>arguments to prove simple curiosities. and perhaps THIS is what
>outsiders complain about.

but wish to emphasize that I regard the *complexity* of priority/injury
arguments as the ONLY reason to avoid them.  Simpson goes too far in his
concern about whether such arguments can be "cleansed" from a proof; the
simplest or easiest arguments for any particular proof are the best
ones, and the simplicity that counts here is the expert's.  In other
words, a proof of a result outside of classical recursion theory that
uses a standard recursion-theoretic technique like finite injury in a
straightforward way is a good proof; the complexity of teaching the
reader the finite injury priority method should not count towards the
complexity of the proof!  A proof that uses recursion-theoretic
techniques in an extremely complicated way (for example Cooper's proof
of the non-rigidity of the r.e. degrees, which I am told is still in the
process of being accepted because of its length and difficulty) is
unsatisfactory because of this complexity, not because of the specific
techniques used.

-- Joe Shipman