FOM: (non)computability
Stephen Fenner
fenner at cs.sc.edu
Thu Sep 10 10:40:00 EDT 1998
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
More information about the FOM
mailing list