FOM: what is computability theory?

[Stephen G Simpson]

Larry Stout writes:
 > May I suggest looking at Douglas Bridges {\bf Computability, a
 > Mathematical Sketchbook} Springer Verlag, Graduate Texts in
 > Mathematics.

I can't get to a library right now.  Tell me, does Bridges' textbook
contain a definition of the term "computability theory"?

Martin Davis writes:
 > The short answer to this question is it is the same subject hat
 > used to be called "recursive function theory" and then
 > metamorphosed to "recursion theory". ....

Are you sure that "computability theory" (as discussed by Soare in his
1995 position paper) is the same subject as recursion theory?  For
example, does it include asymptotic computational complexity theory,
or doesn't it?  Soare chose to waffle on this important point.  (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.)

We could also discuss this from another angle: the historical or
sociological one.  When asymptotic complexity emerged as a new subject
in the 1960's, why was it scorned by recursion theorists such as
Sacks?  Do the recursion theorists now regret that decision?  Does
Soare's 1995 position paper reflect a desire to reverse that decision?
Or does it reflect a desire to obfuscate that decision?

 > In my old book I favored "semi-computable" rather than r.e. as a
 > more appropriate term. (E.g. what enumerates the empty set?
 > Kleene's IM doesn't accept the empty set as being r.e..) (I don't
 > at all like Soare's "c.e.")

I too prefer "semi-computable" or "semi-recursive" to c.e. or r.e.,
for the reason you mention.  Another advantage of the "semi-"
terminology is that it works better in Kleene/Platek higher type
recursion theory, where enumerability doesn't play a big role.

 > I fail to understand why Steve is so exorcised over the matter.

Here are two reasons why I'm so indignant about Soare's 1995 position
paper.

1. Recursion theory as practiced by Soare and his group is concerned
exclusively with the study and classification of *non-computable* sets
(both semi-computable and otherwise).  To insist on calling this
subject "computability theory" (if that's what Soare is doing) strikes
me as extremely odd and perhaps intentionally misleading terminology.
It's as if classifiers of rocks and other inanimate objects were to
try to increase the prestige of their subject by renaming it
"biology".

2. I find it somewhat obnoxious that Soare proposes to stake out some
academic turf and call it "computability theory" without ever defining
the extent of the turf, i.e. the scope of the subject.  Indeed, he
seems to be deliberately obfuscating this issue, as I explained near
the end of my earlier posting on this subject.

I plan to elaborate further on these themes.  But first, I'd
appreciate an answer to my specific question: Does "computability
theory" include asymptotic complexity theory, or doesn't it?

-- Steve