FOM: what is computability theory?

[Stephen G Simpson]

Let me sum up my view of this, making use of conclusions reached in
the discussion so far.

First, let me compare two specific subjects: (1) asymptotic
computational complexity; (2) r.e. sets and degrees of unsolvability.
These two subjects have a somewhat complicated relationship, which can
be summarized by saying that they are separate yet close enough to be
introduced in the same textbook.  (This is a paraphrase of Martin
Davis in 23 Aug 1998 11:36:58.)  On the one hand, they share a common
conceptual base (Turing machines or whatever), and there are
significant analogies (e.g. NP-completeness as a feasibility analog of
Turing completeness or 0'; the PTIME hierarchy as a feasibility analog
of the arithmetical hierarchy).  On the other hand, the methods are
largely different (priority arguments vs gritty combinatorial
arguments), the objects of study are almost completely different
(non-recursive sets vs feasible and non-feasible recursive sets), and
the goals are almost completely different (e.g. classification of
non-recursive r.e. sets vs classification of feasible and non-feasible
but solvable problems).  A further complication is that these two
subjects are usually taught in different university departments:
degrees of unsolvability and r.e. sets is usually taught in pure
mathematics departments as a pure mathematics subject; computational
complexity is usually taught in computer science departments as the
basic framework for a very practical or applied subject, analysis of
algorithms.

What about future evolution of these two subjects?  They seem to be
moving in orthogonal directions: approximate algorithms in complexity,
structural questions in r.e. degrees.  Of course I'd love to see the
recursion theorists take an interest in f.o.m. and eventually embrace
reverse mathematics as "the new recursion theory", as Harvey advocated
in 2 Aug 1998 21:51:35, but that is turning out to be a slow process.
What about big open problems?  From a general scientific point of
view, I think the P=NP problem is several orders of magnitude more
shattering in its implications than any specific open problem in
degrees of unsolvability and r.e. sets.  On the other hand, if someone
can make progress on why incomplete r.e. sets don't arise in nature,
then that could conceivably be very interesting too.

So far as nomenclature goes, I plan to keep using "recursion theory"
to refer to degrees of unsolvability and r.e. sets, as I learned from
my teachers Hartley Rogers and Gerald Sacks.  I'm not convinced that
there is any intellectual need to have an overarching term that would
cover both this subject and asymptotic complexity and perhaps other
computer science topics.  If there really is such a need, then perhaps
the name "computability theory" would do, provided the mathematicians
and the computer scientists can agree on it.  However, Soare's 1995
position paper waffled on this point, deliberately it seems to me.  I
don't want to spread confusion by talking about "computability theory"
in the absence of public, interdisciplinary agreement about what that
term covers.  A further difficulty so far as I am concerned is that
this possible use of the term "computability theory" would be
inappropriate, because degrees of unsolvability and r.e. sets deal
mainly with non-computable things and have only the most tenuous
relationship to actual computing.  I think this is similar to G"odel's
point in the anecdote that Martin Davis related.

-- Steve