FOM: Recursive vs Computable

[Joseph Shoenfield]

     The dispute over replacing "recursive" by "computable" has irrupted
in fom just as it was quiting down in recursion-theoretic circles.   I
have no wish to revive it, but I cannot resist giving a summary of the
dispute as I see it.
     Bob Soare was the first to seriously propose the change.   He was (I
think) motivated to consider the change by some events which seemed to
show that recursion theory was not receiving its just share of resources
and the observation that anything connected with computers generally
received at least its just share.   He extensively investigated the period
in which recursion theory received this name and the forcefully proposed
his change to recursion theorists in articles, letters, conversations,
etc.   The reaction was quite varied; it included enthusiastic acceptance,
outright rejection, indifference, and other shades of opinion.
     I was one of the rejectors.   My principal reason was adherence to
the principle that established terminology should not be changed without
overwhelming evidence for the change.   Of course, Bob felt that his
evidence was overwhelming; but I felt that in interpreting the historical
evidence, he was unduly influenced by his desire for the change.   For
example, in his interpretation of the early days of recursion theory, he
sees Godel and Turing as the leading figures and Church and Kleene as
lesser figures.   I think that the opposite is true.   This is not to deny
that Godel's insight into logical matters is exceptional or that his proof
of the incompleteness theorem contained the seeds of some of the most
important developments of recursion theory; but I think that his role in
the period in which Church's Thesis became accepted does not show him at
his best.
     My objection to replacing "recursive" by "computable" is much
stronger in some cases than others.   Replacing "recursion theory" by
"computability theory" is not entirely unreasonable; as others have
observed, many of the titles of classical works on recursion theory
include the phrase "computability theory".   On the other hand,
replacement of "recursively enumerable" by "computably enumerable" seems
to me to be absurd.   I don't think this term was ever used before this
dispute.   I think that many students familiar with RE sets must have been
puzzled by suddenly seeing articles on CE sets.   In one such article,
there was a footnote suggesting than one of the joint authors felt the
change of terminology was important and that the other consented because
he did not think the matter was of any importance.  I think that things
like this, far from increasing the support of recursion theory, will make
it seem ridiculous.   In the names of several conferences, "recursion
theory" was changed to "computability theory"; in at least one case, the
conference organizers gently suggested to the participants that they
change their titles correspondingly.    I think conference organizers
should stick to the accepted terminology until a change has been approved
by a consensus of experts in the field.
     Steve asks supporters of the change to provide a definition of
"computability theory" and in particular to state whether complexity
theory is a part of computability theory.   I agree completely with Jones
that the supporters of the change advocate not replacing one theory by
another but renaming a theory.   Thus I think they would say that
complexity theory is a part of computability theory if and only if it is a
part of recursion theory.   I think that complexity theory is a part of
recursion theory because it makes strong use of the concepts and methods
of recursion theory.   I do not base this on a particular definition of
recursion theory; I think that one shoud decide what topics are a part of
recursion theory BEFORE one attempts a definition of recursion theory.
(I think Steve is mistaken in asserting that most recursion theorists do
not think that complexity theory is a part of recursion theory.)
    Supporters of the change correctly assert that the name "recursion
theory" was originally attached to the theory for accidental reasons, and
that the central concept of the subject at that time was computability,
not recursion.   I don't think this is a good reason for changing the name
sixty years later.   In any case, it is a remarkable coincidence that
about the time Soare and others were making this argument, many recursion
theorists were becoming convinced that recursion is indeed one of the
fundamental notions of recursion theory.   I will write about this in
another communication, since I dson't think it has anything to do with
this dispute.
     I am much more sympathetic to the replacement of RE by semirecursive.
In classical recursion theory, RE has (at least) 3 equivalent definitions:
(i) equal to the range of a (partial) recursive function; (ii)equal to the
domain of a partial recursive function; (iii) sigma-0-1.   All of these
have their uses.   In higher type recursion theory, these 3 concepts
diverge.   Workers in the field agree that the concept defined by (ii) is
the one which has the most impotant features of RE sets in higher types.
Most of them use the term semirecursive for this concept.   Some (like
Sacks) simply use RE for this notion.   There are some advantages to using
semirecursive.   A notion with a definition similar to (i) is of use in
set recursion; perhaps it is best to reserve "enumerable" for this notion.
Moreover  semirecursive is shorter than recursively enumerable.   Why use
two words for a theory which is well-described by one?   In any case, this
change would not be a change of established terminology, since the
meaning of RE in higher types has never been agreed upon.