FOM: priority arguments in applied recursion theory
Stephen G Simpson
simpson at math.psu.edu
Wed Jul 28 15:12:36 EDT 1999
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
1. WHAT IS A ``PRIORITY METHOD''?
> 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
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.
Is this an example of a ``priority method''?
2. PRIORITY ARGUMENTS IN COMPUTATIONAL COMPLEXITY
> 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?
Name: Stephen G. Simpson
Position: Professor of Mathematics
Institution: Penn State University
Research interest: foundations of mathematics
More information: www.math.psu.edu/simpson/
More information about the FOM