FOM: what is computability theory?

Stephen G Simpson simpson at
Tue Aug 18 17:08:47 EDT 1998

This posting is in part a follow-up to the earlier discussion of
recursion theory versus asymptotic complexity theory.  See the last
few paragraphs below.

A few years ago, a group of recursion theorists decided to repackage
their subject as "computability theory".  But what is computability
theory?  I think I know what recursion theory is: it's the subject
that I learned from Hartley Rogers and Gerald Sacks: relative
recursiveness, degrees of unsolvability, recursively enumerable sets.
My question now is, is computability theory the same subject, or a
different one, or perhaps a broader one?

Peter Cholak maintains a Computability Theory web site at  However, I searched that
site in vain for a definition of the term.  There is a list of "people
who work (or have worked) in computability theory."  So far as I can
tell from that list, the web site is concerned exclusively with
recursion theory in the Hartley Rogers sense.

The argument for the switch to "computability theory" was spelled out
in Robert I. Soare's 1995 position paper "Computability and
Recursion", available on-line at (PostScript
file).  Soare is a leading recursion theorist, and his 1987 book
"Recursively Enumerable Sets and Degrees" is definitive in that area.
The 1995 paper focuses on public relations, specifically on how "the
subject" (recursion theory?) is perceived by laymen.  It spends 47
pages arguing that "computability" is a less confusing term than
"recursion", because it evokes Turing machines or register machines
rather than inductive definitions or recursion equations.

I was disappointed to find that Soare's 1995 paper, like Cholak's web
site, contains no definition of computability theory, not even a stab
at one.  There is a short section entitled "Themes and Goals of
Computability Theory," but that section consists mainly of a long list
of diverse topics that "should be considered a mixture of concepts,
goals, themes, and connections with other areas."  The term
"computability theory" itself is never defined.

The only point that Soare insists on is that computability includes
relative computability, i.e. relative recursiveness as a means of
classifying non-recursive sets.  This terminology strikes me as
wrong-headed, as if one were to insist that biology includes the study
and classification of inanimate objects.

Soare's list of "themes and connections with other areas" includes
asymptotic computational complexity (P=NP, etc.), and other parts of
computer science.  I'd like to ask one specific question: Is
asymptotic computational complexity theory part of computability
theory, or isn't it?

As I study Soare's paper, I get the feeling that his intention is is
to keep the term "computability theory" ambiguous or elastic.  In some
forums, he will use it to refer to recursion theory, i.e. degrees of
unsolvability and r.e. sets, but in other forums he wants the freedom
to hint or imply that it includes subjects like asymptotic
computational complexity, or maybe all of computer science and
numerical analysis.  Apparently his motive is to try to boost the
prestige of recursion theory.  If that's his goal, then clearly this
is not the way to achieve it.  Such an approach will inevitably
backfire and make recursion theorists look like academic charlatans.

Be that as it may, could somebody please tell me: 

             What is computability theory?
-- Steve

More information about the FOM mailing list