FOM: (non)computability

[Stephen Fenner]

Stephen Fenner                       803-777-2596
Computer Science Department          fenner at cs.sc.edu
University of South Carolina         http://www.cs.sc.edu/~fenner
Columbia, SC  29208  USA

Way back on Wed, 2 Sep 1998, Joe Shipman wrote:

> Fenner writes:
> 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.

True, but in the practical world, computers get information from all
sorts of sources that are not computable functions in the standard sense:
user input, microphones, cameras, seismometers, etc., and we still label
it "computation."   The label refers to what the computers *do* with
the data; where the data comes from is irrelevant.

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

Agreed.

> However, the *practical* relevance is utterly different.  Does
> ANY result in the theory of degrees of unsolvability have practical
      ^^^^^^
> applications?

Results -- no.  Techniques -- definitely (taking your use of "practical"
in maybe a broader sense).  For instance, I and some others have used a
lot of forcing arguments in complexity theory over the years, and I think
that they really illuminate many issues related to polynomial-time
computation.

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

I completely agree.


Steve Fenner