FOM: recursion theory and computer science; Downey/Kurtz

[Stephen G Simpson]

This is a partial response to Stuart Kurtz, FOM 6 Aug 1999 11:08:47.

Kurtz says:

 > Point 1.  While computability theory originated in the study of the
 > foundations of mathematics, it is now a part of the foundations of
 > other applied fields.

The term ``computability theory'' is somewhat ambiguous (see for
instance FOM 23 Aug 1998 13:36:53) but for discussion let's take it to
be the subject sometimes known as recursive function theory, defined
by Martin Davis's classic textbook ``Computability and
Unsolvability'': Turing machines, general recursive functions, the
rudiments of partial recursive functions and r.e. sets, etc.

With the above definition of ``computability theory'', point 1 is
indisputable.  Turing's fundamental work on unsolvability of the
halting problem and related results are firmly entrenched in the
computer science curriculum, and deservedly so.  This stuff is part of
the foundations of computer science and is basic for every theoretical
computer scientist.

 > The mathematical science of computation, founded in large part on
 > computability theory, overlaps the current disciplinary boundaries
 > of mathematics and computer science.

The phrase ``mathematical science of computation'' is again ambiguous.
Does it include numerical analysis?  Numerical linear algebra?  The
finite element method?  At any rate, it is certainly true that both
computability theory (as defined above) and numerical analysis etc
overlap the disciplinary boundary between mathematics and computer
science.

Let me now make another related point.  This has reference to the
Friedman/Simpson ``defending specialized subjects'' posting (FOM 28
Jul 1999 16:34:09):

 > In the best case, the practitioners of subject X may respond to
 > the critics by reforming or redirecting or recasting subject X in
 > significant new ways, thus giving subject X a new lease on life.

I want to note that an excellent example of this reform process was
seen in the 1960's with the development of computational complexity
theory.  At the time, the theory of general recursive functions
(``subject X'') was coming under criticism for lack of relevance to
actual computation, because of the disavowal of time and space bounds.
A few computer scientists and mathematicians responded by reworking
the basic notions of recursive function theory to incorporate such
bounds.  Thus computational complexity theory was born, and it thrives
to this day as a mainstay of theoretical computer science.  I regard
this reform as a wonderful chapter in the history of recursion theory.

 > This cycle of criticism, reform, criticism, reform, ... can
 > continue indefinitely, to the great benefit of subject X and
 > related academic subjects.

Some people (e.g. Friedman FOM 2 Aug 1999 11:14:00) might say that
recursion theory is now in the midst of another crisis and in need of
further reforms.

Kurtz continues:

 > Point 2.  The principle technologies of modern computability theory
 > are used in applied settings.

Here Kurtz is returning to the earlier FOM discussion of the role of
priority arguments.  Kurtz's collapsing degree example has already
been discussed here on FOM (see 28 Jul 1999 15:12:36 and 4 Aug 1999
19:18:00).  I now want to comment on another of Kurtz's examples:

 > c. Downey-Kurtz proved that there is a computable torsion-free
 > abelian group that is not computably linearly ordered.  This shows
 > that the classical theorem that every torsion-free abelian group
 > can be ordered is nonconstructive.

Yes, this was first done with a priority argument.  However, it was
subsequently done better without one.  Inspired by the recursive
counterexample of Downey/Kurtz 1986, Hatzikiriakou/Simpson 1990 (see
page 143 of my book) proved that ``every torsion-free Abelian group
can be ordered'' is equivalent over RCA0 to WKL0.  This reverse
mathematics result was proved without a priority argument and
immediately implies the Downey/Kurtz result.

I would love to see a really good example of an essential use of a
priority argument to obtain a ``recursive counterexample'', i.e. a
result showing that some well-known mathematical theorem is
nonconstructive because it fails in the world of recursive functions.

A partial apology:

Some FOM readers may think that I am overly concerned with the issue
of when priority arguments are eliminable.  And perhaps I *am* too
concerned with this issue.  If so, I apologize for taking up so much
bandwidth on this.  A partial excuse is that I inherited this issue
many years ago from my thesis advisor, Gerald Sacks.  I think it is
fair to say that Sacks was obsessed with methodological issues in
recursion theory, including distinctions between different kinds of
proof methods -- diagonal, wait-and-see, finite injury, infinite
injury, etc -- and the question of what kinds of problems required
these various techniques in order to solve them.  Recall the passage
in Sacks' monograph on degrees of unsolvability where he says
something like ``we regard a problem as interesting only if its
solution requires a new method''.  I never concurred in that
sentiment, but the issue of what kinds of problems require priority
methods for their solution remains interesting to me.  Perhaps the
currently dominant group of hard-core recursion theorists does not
share this interest.

Kurtz continues:

 > Priority arguments are not the only technique whereby computability
 > theorists produce sets with interesting computational properties.

Yes, I completely agree.  Recursion-theoretic methods other than
priority methods are often useful in theoretical computer science.
The earlier discussion (e.g., FOM 4 Aug 1999 19:18:00) was only about
priority arguments, not about other recursion-theoretic methods.

-- Steve