FOM: (non)computability

[Joe Shipman]

Fenner writes:
  At the heart of almost any good proof in recursion theory
is one or more algorithms.  These algorithms may be showing that one
particular degree is higher than another, and both may be noncomputable.

I consider *relative* computation to be computation just as much as
absolute computation, and so much of recursion theory (at least
classical
recursion) is still about computation.

   Very interesting remark.  Of course the concept of "subroutine" is
fundamental to computation, so in that sense "relative" computation is
still computation.  But if you replace "subroutine" with "oracle" the
connotations become different, because the "oracle" isn't necessarily a
computable function.  Since "oracle arguments" are at the heart of much
computational complexity theory, the technical resemblance between
complexity theory and recursion theory is still strong (though there is
much more to complexity theory that has no analogue in recursion
theory).  However, the *practical* relevance is utterly different.  Does
ANY result in the theory of degrees of unsolvability have practical
applications?
   This is not meant as a criticism of recursion theory, I just want to
point out that betwen recursion theory and complexity theory there is an
important sociological gap (the old pure-applied distinction in rather
stark form).
   The gap is not unbridgeable.  Complexity theory certainly includes
work with no practical application (for example on problems with
super-exponential complexity) which makes the division between
"computable" and "noncomputable" seem somewhat arbitrary (you could draw
the boundary at primitive recursion instead of general recursion for
example).  But the existence of this gap and the rather clear partition
it induces on the set of researchers suggests that it makes pragmatic
sense to speak of two subjects rather than one ("complexity theory" and
"recursion theory" rather than "computability theory").

-- Joe Shipman