FOM: what is computability theory?

[Martin Davis]

At 09:48 PM 8/24/98 -0400, simpson at math.psu.edu wrote:

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

I think this is the crux of our disagreement: it is so clear to me that this
is not at all a different subject, that it took me a long time to absorb the
fact that you think they are different. The text book I referred to
COMPUTABILITY COMPLEXITY & LANGUAGES in its first edition covered degrees
and included a priority argument (Sack's splitting theorem). If you can find
a copy, perhaps you can tell me where, in what I regard as a seamless
exposition, computability theory ends and recursion theory begins. [If you
wonder why the degrees were dropped from the second edition, it was with
regret. Our third author Ron Sigal was welcomed aboard to do most of the
work on the second edition, and his condition was that he could include
material on denotational semantics. So some material had to be dropped
because otherwise the book would have been too long.]

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

He would have been too shocked at being addressed by his first name to respond.

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

I'm being seriously misquoted. I said (at some length) that the question is
ill-defined. The subject clearly drew much of its inspiration from
computability theory, and analogies played a large role in the key
definitions. In the textbook I keep bringing up, notions of reducibility are
introduced in a unifrom way so that many-one reducibility, Turing
reducibility, and polynomial time reducibility are seen as special cases of
a general notion, and a few of the simplest propositions are derived in a
way that applies to all three. Does that make them all part of the same
subject? And of course the P-time hierarchy is defined in a clear analogy
with the arithmetic hierarchy.

I disagree with Joe when he says that the methods are similar. My sense (and
I'm not such an expert) is that argument in complexity theory tend to be
down-and-dirty combinatorial in nature, especially the stuff about circuits.