FOM: priority arguments in applied recursion theory

[Stephen G Simpson]

This FOM posting responds to two points in Robert Soare's FOM posting
of 27 Jul 1999 14:03:43, which consisted of a message from Stuart
Kurtz.

1. WHAT IS A ``PRIORITY METHOD''?

Kurtz said:

 > I do not know whether or not there is an intellectual linkage
 > between priority methods in computability theory, and in
 > programming practice; but I do know that the use of priority
 > methods in practice is real.

It appears that Kurtz is proposing a broader concept of ``priority
method'', under which it can be said that priority methods are
routinely used in programming practice.

Thus, in order to continue the discussion of the so-called Simpson's
Thesis, it now becomes necessary to agree on a more exact notion of
what we mean by ``priority method''.  This may not be easy.  I know
that there have been some interesting but perhaps not entirely
conclusive attempts at a mathematically rigorous definition of
``priority method''.

Let me pose the following non-rigorous but serious question for Soare
and Kurtz and other recursion theorists:

Background of my question:

  Suppose I make myself a ``to do'' list, e.g., a list of tasks that I
  want/need to finish this summer, before the start of the next
  academic year.  It may include tasks such as: (1) finish writing my
  CTA paper, (2) answer numerous private e-mails from Soare, (3) write
  a referee report, (4) get a haircut, etc etc.  And suppose I order
  these tasks in various ways, e.g. in terms of importance, amount of
  time needed to complete, etc., and systematically arrange them in
  such a way that I will be able to accomplish them in a desirable or
  efficient manner, barring unforeseen circumstances.

My question: 

  Is this an example of a ``priority method''?

2. PRIORITY ARGUMENTS IN COMPUTATIONAL COMPLEXITY

Kurtz said:

 > I don't have a reference for Homer-Maass close at hand.  I'm sure
 > that Steve can provide.

Is this referring to Steve Fenner, or to me?  If it's me, then I am at
a loss, because I wasn't part of what was apparently an earlier
discussion of Homer-Maass between Soare and Kurtz.

 > By using a priority argument, we were able to demonstrate that a
 > collapsing degree exists in exponential time

This together with Fenner's FOM posting of 26 Jul 1999 16:44:06 seems
to suggest that collapsing degrees are one area of computational
complexity theory where priority arguments play a significant role.
Are there other such areas?  

What about the question that I raised in my 27 Jul 1999 16:15:06
response to Fenner:

 > what about the ratio of papers in theoretical computer science (or
 > perhaps even computational complexity theory) that use priority
 > arguments, to those that don't?  My impression is that this ratio
 > is rather small.  Is it as high as 1/10 of a percent?  

-- Steve

Name: Stephen G. Simpson
Position: Professor of Mathematics
Institution: Penn State University
Research interest: foundations of mathematics
More information: www.math.psu.edu/simpson/