FOM: recursion/computability/complexity theory

[Stephen Fenner]

I've been reading the discussion about recursion theory versus complexity
theory with much interest.  I've done work in both areas, but unlike
Wolfgang Maass, I started in complexity theory then learned recursion
theory along the way (at U Chicago).
     There seems to me (and to others) to be a split in complexity
theory between what I'll call "low level" complexity and "structural"
complexity.  Low level theory addresses questions about circuits and other
"hardware-like" things, and depends heavily on combinatorics.  Structural
complexity deals with more conventional complexity classes (such as P and
NP) and hierarchies, and borrows a lot of techniques from recursion
theory.  Mahaney's theorem, mentioned in earlier posts, falls into this
subset. These two subareas often have separate conferences and workshops,
and I don't know many who are contributing to both areas right now.
     My work is in the latter area, and I find so much of what I do
recursion-theoretic that the distinction between recursion and complexity
theory is very blurry for me.
     I wouldn't call the whole of complexity theory a subset of recursion
theory by any means, but structural complexity is pretty close.  When a 
recursion theorist asks me what complexity theory is about, my short
answer is that it studies the fine structure of 0.

     Anyway, I can't resist adding my $0.02 re the names recursion versus
computability to name the theory.  Shoenfield's points regarding
recursion/definability's role in developing significant aspects of the
theory (HYP for example) are well-taken.  I do, however thing that Soare's
proposal has merit (and not just because I come from U Chicago ;-), both
from a PR and descriptive point of view.  The PR advantage is clear, I
hope.  Moreover, computability is more descriptive.  Stephen and Harvey's 
preference for "noncomputability" over "computability" misses the point
in my view.  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.
     I do tend to side with Shoenfield more regarding the recursion
theorem.  My understanding is that Soare proposes that this be called the
"fixed-point theorem."  The old name seems so much more natural,
especially considering the average computer science student's notion of
recursion.  Furthermore, the two forms of the recursion theorem that
Shoenfield mentions have complexity-theoretic analogues that are *not*
equivalent.  In exponential-time computation, there is a recursion theorem
but no fixed-point theorem.


Stephen Fenner
fenner at cs.sc.edu
http://www.cs.sc.edu/~fenner