FOM: what is computability theory?

[Stephen G Simpson]

Martin Davis writes:
 > On computability,I made a number of substantive points which I
 > don't believe you ever answered. In particular that the word has
 > been used in the computer science community for decades with no
 > confusion.

Well, that's not really a substantive point; it's a terminological
point.  But I'll answer it anyway.

The computer science community has used "computability theory" to
refer to the study of computable functions obtained from Turing
machines or whatever.  This is a reasonable name for a traditionally
important topic in theoretical computer science.  Using this name for
it has not caused confusion in the computer science community.

On the other hand, Soare and his group now want to use "computability
theory" to name a somewhat different subject: degrees of unsolvability
and the lattice of r.e. sets.  This strikes me as very misleading
terminology.  Outsiders will surely be misled.  The old name
"recursion theory" is opaque and therefore not so misleading; see
Peirce's remark.

 > 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.

I wish you had tried that argument on G"odel in 1953.  "Kurt, don't
you know that a priority construction is an algorithm for enumerating
a RECURSIVELY ENUMERABLE set?  And degrees of unsolvability is the
study of RELATIVE RECURSIVENESS.  It beats me why you object to
calling this stuff recursive function theory."  What do you think
would have happened if you had said that to G"odel?

:-)

By the way, it seems there is still disagreement about whether
recursion theory (a.k.a. computability theory) includes asymptotic
complexity or not.  Martin Davis says it doesn't, while Joe Shoenfield
says it does.  Maybe we just have to accept the fact that it's an
amoeba-like subject, sending out pseudopods at will.

-- Steve