FOM: what is computability theory?

[Stephen G Simpson]

Martin Davis writes:

 > I heard the same objection from G\"odel (in ~1953), but ir was to
 > the (then current) term "recursive function theory". He objected to
 > using it for the study of non-recursive things. He mentioned Rosza
 > Peter's work as properly being recursive function theory.

G"odel's objection makes perfect sense to me.  And clearly the same
objection ought to apply to "computability theory" as a name for the
study of non-computable things.  And, just as in G"odel's remark on
Rozsa Peter's work (hierarchies of multiply recursive functions, etc),
by the same token one also ought to mention axiomatic computational
complexity (P=NP etc) as being properly part of computability theory.
Martin, don't you agree?  These were some of my objections to Soare's
terminology, so it seems to me that my views are completely in tune
with those of G"odel!

Oddly enough, Soare in his 1995 position paper also cites your G"odel
anecdote, but he gives it a completely different twist!  In arguing
for his proposal to repackage "recursion theory" as "computability
theory", Soare says:
 
  Both Turing and G"odel, even later in life, rejected "recursive" as
  a name for the subject and often for their results. ....  In the
  three volumes of his collected works, G"odel *never* used the term
  "recursive function theory" to name the subject; when others did
  G"odel reacted sharply negatively, as related by Martin Davis. ....
  In spite of the strong preference for "computable" by Turing and
  G"odel, the founders of the two formalisms and concepts, the name
  "recursive" instead of "computable" has been associated with almost
  all objects of the subject since the 1930's. ....

Martin, what do you think of this?  Did G"odel propose to use
"computability theory" to designate the study of non-computable
things?  Just the opposite, right?  If so, then shouldn't you be
strenuously objecting to Soare's misuse of your anecdote?

By the way Martin, you never answered my specific question: In your
terminology, is asymptotic complexity theory part of computability
theory, or isn't it?

 > Steve: Do you also then object to Roger's title for a book that is
 > largely about non-computable things?

I always felt that Rogers' title "Theory of Recursive Functions and
Effective Computability" was somewhat misleading, for this very
reason.  On the other hand, your title "Computability and
Unsolvability" and Sacks' "Degrees of Unsolvability" are fine with me,
because they explicitly mention unsolvability.

Vladimir Sazonov writes:
 > > (I take it as a given that recursion theory *does not* include
 > > asymptotic complexity theory.  I learned this from my thesis
 > > advisor, Gerald Sacks, in the late 1960's.)
 > 
 > Would you recall the arguments of Sacks (or yourself)?

I don't think Sacks offered any argument.  He simply declared it.  And
he had no interest at all in asymptotic complexity theory.  His main
interests at the time were degrees of unsolvability, generalized
recursion theory, and model theory.

My own view is that it makes no sense to use terms such as "recursive
function theory" or "computability theory" to designate a subject that
includes degrees of unsolvability but excludes axiomatic complexity
theory.  I find the term "recursion theory" less objectionable,
because it is vaguer.

-- Steve