FOM: computability & complexity

[Martin Davis]

Steve Simpson wrote:

>As evidence that there is a lot of confusion here, let me recall that
>Martin Davis and other computability theorists have been unable to
>answer my specific question: Does computability theory include
>asymptotic complexity theory, or doesn't it?  It appears that this
>question is somehow embarrassing for them. 

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.

Steve seems to inhabit a world in which subjects have carefully delimited
contents and boundaries. This is not the world in which I live. I have a
textbook in print (with co-authors Sigal and Weyuker) called COMPUTABILTY,
COMPLEXITY AND LANGUAGES. When we wrote it, we evidently thought that
complexity theory was enough of a separate subject to be entitled to one of
the title-words. On the other hand, close enough to be in the same book. The
chapter on Blum-style complexity (now regarded as terribly old-fashioned, a
status topics in CS attain with frightening rapidity), could certainly be
regarded as part of computability theory. Asymptotic complexity theory has
the following relation to core computability theory: while many of the
concepts and problems are derived by analogy with corresponding topics in
computability theory, the methods that have been found useful are quite
different.

Another topic on which Steve challenged me was on whether given G\"odel's
judgment that "recursive function theory" should designate the study of
sub-recursive hierarchies, would I think G\"odel would accept the
designation "computability theory" for a subject largely devoted to
non-computable things. Not having access to a seance, I can't answer the
question. But the analogy between the two cases is pretty weak. 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.

Let me also point out that the priority constructions that are the hallmark
of the study of r.e. degrees are presentations of ALGORITHMS. The study of
Turing degrees is the study of RELATIVE COMPUTABILITY. It beats me why you
should regard calling these things part of computability theory is some kind
of aggrandizement.

A final question for Steve: in your neat universe is the theory of algebraic
function fields part of: algebra? algebraic geometry? analysis? applied
model theory? none of the above?

Martin