FOM: priority arguments in applied recursion theory

[Stephen G Simpson]

Rod Downey (FOM, 22 Jul 1999 12:17:13) argues against what has now
come to be called Simpson's Thesis, i.e., my observation (FOM, 21 Jun
1999 21:36:37) that

  ``priority methods are almost completely absent from applied
  recursion theory.''

Thank you, Rod, for a valuable FOM posting.  I hope this will be the
start of a thorough discussion, and I hope recursion/computability
theorists will view it as an opportunity to explain what they mean by
``applied recursion/computability theory'' and how various
recursion-theoretic concepts/results/methods (including priority
methods) come in.

First of all, I think everyone agrees that priority arguments are
*much less* prevalent in ``applied recursion theory'' than in the
``pure'' theory of r.e. sets, r.e. degrees, etc.  That contrast was my
original point in stating Simpson's Thesis, and I think it is a valid
and important point for anyone interested in recursion/computability
theory to keep in mind.

Nevertheless, it may still be worthwhile to examine Simpson's Thesis
as an isolated proposition, apart from ``pure'' recursion theory.

First, let's get clearer on what we mean by ``applications''.  In my
original remarks (FOM, 21 Jun 1999 21:36:37), there was room for
misunderstanding because my definition of ``applied recursion theory''
was not very precise.  I defined it as

 > recursion theory connected to issues and programs in f.o.m. and
 > other areas, including: recursive mathematics, intuitionistic
 > mathematics, constructive mathematics, reverse mathematics,
 > theoretical computer science, undecidable problems in mathematics,
 > etc.

and this was not perfect because, in the first place, the ``etc''
could conceivably cover a lot of other areas that might be called
application areas.

Furthermore, my reference to ``recursive mathematics'' was ambiguous,
because there are various schools (the Russian school, etc.), with
various goals and programs.  

What I had in mind by ``recursive mathematics'' is what is sometimes
called *recursive analysis*, i.e., analysis done in a recursive
functions framework replacing the real number system by the recursive
real number system, etc., the goal being to prove recursive analogs of
the theorems of ``classical analysis'' when possible, and to give
recursive counterexamples otherwise.  This subject is expounded in two
books that I am familiar with:

  O. Aberth, Computable Analysis, McGraw-Hill 1980

  M. B. Pour-El and I. Richards, Computability in Analysis and
  Physics, Springer, 1988.

Now, with that clarification in mind, I think it's correct to say that
there are no priority arguments in these two books and few if any
priority arguments in this general area, recursive analysis.  (Are
there more recent books or results in recursive analysis which use
priority arguments?  If so, I would like to hear about them.)

Furthermore, priority arguments also seem to play a very small or
nonexistent role in the other ``applied'' areas that I mentioned:

  intuitionistic mathematics (Kleene realizability, etc; see
  Troelstra/van Dalen, 1988)

  constructive analysis (see Bishop/Bridges 1985.)

  constructive algebra (Richman et al, ...)

  reverse mathematics (see my book ``Subsystems of Second Order
    Arithmetic'' <http://www.math.psu.edu/simpson/sosoa/>, 1999)

  theoretical computer science (At least the standard textbooks on
    computational complexity etc do not use priority arguments.)
    
  undecidable problems in mathematics (Diophantine problems,
    combinatorial group theory, etc.)

But the recursion/computability theorists may want to dispute at least
some of this, and I welcome further discussion.

In order to deal seriously with the issues raised by the so-called
Simpson's Thesis, we need a breakdown of the areas that might be
called ``applied recursion theory'', and then an examination of where
and how priority arguments are used in those areas.  We must also be
careful to distinguish different *types* of ``applications''.  To
quote from my message of a few days ago (FOM, 15 Jul 1999 22:33:53):

  If we are going to compile lists of ``applications'' of recursion
  theory, [...] then we ought to classify them carefully and
  distinguish various features, just as the applied model theorists
  do.  For each ``application'' of recursion theory, we need to say
  what the field of application is, whether the statement of the
  result or only the proof involves recursion-theoretic concepts,
  which recursion-theoretic concepts and/or methods and/or results are
  used, whether the recursion-theoretic concepts and/or methods and/or
  results can be eliminated, what are the costs of eliminating them,
  etc.  There are many distinctions to be made, and these distinctions
  are of essential scientific importance.  It is misleading to lump
  everything together as ``applications'' without further
  qualification.
  
For example, Downey mentioned 

    computable model theory
  
    computable linear orderings
  
    computable Boolean algebras
  
    jump degrees of structures
  
and it is true that priority arguments are used extensively in these
areas.  For instance, in computable model theory, there is
Harrington's old result characterizing when a decidable theory has a
decidable prime model, proved by means of a priority argument, which I
always present in my model theory course; see
<http://www.math.psu.edu/simpson/courses/math563/>.

However, there is a serious and legitimate question of whether results
in these areas are properly called *applications* of recursion theory.
This is because the results themselves, and even the questions
answered by the results, always mention recursion-theoretic concepts
and often even mention advanced recursion-theoretic concepts.
Contrast this with applied model theory, where one does not speak of
an ``application'' unless first-order formulas and other logical or
model-theoretic concepts are absent from the statement of the result.
In the present context, it seems more legitimate to speak of
``connections'' between recursion theory and other parts of
mathematics, rather than ``applications'' of recursion theory.  In any
case, the distinctions that I drew above are obviously relevant.  See
also Harvey Friedman's discussion of the so-called ``Simpson's
Thesis'' (FOM, 19 Jul 1999 12:33:44).

Another ``applied'' area is recursive algebra a la Metakides/Nerode,
Remmel, Kalantari, Smith, et al.  Here my experience has been that
priority arguments are often eliminable and in these cases the proofs
are presented more clearly without them.  For example,
Metakides/Nerode (Annals of Math Logic 1979) used a priority argument
to construct a recursive infinite-dimensional vector space over the
rationals with no infinite recursive linearly independent set.  This
is a very nice recursive algebra result, but it turns out that a
stronger reverse mathematics result can be proved more clearly without
a priority argument; see section III.4 of my book
<http://www.math.psu.edu/simpson/sosoa/>.

More on the relationship between reverse mathematics and recursive
algebra is in my book and in my FOM posting of 18 Aug 1998 14:10:44.

Additional ``applied'' areas that according to Downey use priority
arguments are

    combinatorial group theory
  
    inductive inference
  
    complexity theory

and here I confess that I am at a loss.  Most textbooks of
combinatorial group theory (Magnus/Karrass/Solitar, Lyndon/Schupp,
...) do not even prove the unsolvability of the word problem for
finitely presented groups.  But Downey mentions results of Higman
(which results???), and

 > Khisamiev's msolution to the problem of Baumslag et al showing that
 > a recursively presented torsion free abelian group'' (in the
 > combinatirial classical nomenclature) is isomorphis to one with a
 > solvable word problem uses a finite injury arument.

I don't know about this.  Could somebody please provide a reference?

In inductive inference Downey says that there are large numbers of
priority arguments, but again I don't know this area.  Do the results
themselves mention recursion-theoretic concepts?  Are the priority
arguments eliminable?

As for computer science, obviously the standard textbooks do not use
priority arguments (look in the computer science section in your
campus bookstore), but Downey says there is newer work:

 > A recent example is by Toueg and Chandra in the use of 
 > failure detectors in asynchronous distribited computing. (Look up
 > failure detector on the web). This came from Chandra 
 > attending a course on CRT by oDIFREDDI.  it is seen as 
 > some of the most important work in years. I think we could offer 
 > a lot in thiat area. 

I followed Downey's suggestion and found titles of papers such as
``Unreliable Failure Detectors for Reliable Distributed Systems''.
But the fact that one of the authors of a paper attended a course by
Odifreddi doesn't tell us whether priority arguments are used in the
paper, whether they are eliminable, etc.  Could someone please clarify
this situation?

By the way, we have had some pretty good discussions of recursion
theory and computer science here on FOM some months ago.

Anyway, that's enough for now.  I hope to continue this discussion
later.

-- Steve