FOM: computability & complexity

[Stephen G Simpson]

Martin Davis writes:
 > Steve, please. I just got back from the airport, sending my
 > grandson home. I was too busy with him to attend to this silly
 > question. It hardly embarrasses me.

Martin, I apologize for misinterpreting your not answering my question
as embarrassment.  But I don't think the question itself is silly.
Imagine a gathering of scientists, say a meeting of the National
Academy of Sciences.  Soare introduces himself as a computability
theorist.  Wouldn't it be natural for the assembled scientists to
assume that his research focus is computation, computer science,
algorithms, or something like that?  In actual fact, computability
theory as practiced by Soare is not terribly close to those areas;
there's a significant disconnect.  My question about asymptotic
complexity was intended as a way of approaching that rather serious
issue.

Anyway, I'm glad you have now answered my question, by acknowledging
that asymptotic complexity theory is a separate subject from recursion
theory, with very different methods, despite the obvious connections.

 > G\"odel could refer to a substantial existing study of recursions
 > of various limited kinds that he thought a more appropriate subject
 > to have the name RFT. There is nothing similar begging to be called
 > computability theory.

What about asymptotic complexity theory and analysis of algorithms?  I
think this begs to be called computability theory, because it's a
theoretical subject dealing with existence and nonexistence of more
and less feasible algorithms for computing various things and solving
various problems.  This is one reason why I don't like Soare's
proposal to use "computability theory" to designate the subject
formerly known as recursion theory.

(By the way, there was a rock star called Prince who changed his name
to something unpronounceable.  He is now known as TAFKAP -- "The
Artist Formerly Known As Prince".  Has anyone started referring to
computability theory as TSFKART?)

 > in your neat universe is the theory of algebraic function fields
 > part of: algebra? algebraic geometry?  analysis? applied model
 > theory? none of the above?

I'm no expert on this, but I would say that the theory of algebraic
function fields is part of algebra.  Of course it has connections to
other areas: it has applications to algebraic geometry (Zariski), and
model theory has applications to it (Hrushovski).  So far as I know,
this agrees with the way the experts see it.

Apart from the issue of "neatness", I do think it's important to
delineate subjects carefully.  This seems particularly important when
it comes to evaluating research.

-- Steve