FOM: priority arguments in applied recursion theory

[Stephen G Simpson]

Concerning my example of an informal to-do list in 28 Jul 1999
15:12:36, Steve Stevenson 28 Jul 1999 16:48:53 writes:

 > Do you (Steve Simpson) call this a priority method?

I myself would certainly *not* refer to an informal to-do list as an
example of a ``priority method''.  In my opinion, to do so would be to
rob the term ``priority method'' of its specific scientific sense.  By
this standard, everybody you know would be using priority methods all
the time, every day.

[ Background: My Ph.D. thesis advisor (long ago) was Gerald Sacks, a
prominent recursion theorist with very strong and specific
methodological ideas about what constitutes a ``priority argument'',
as distinguished from a ``diagonal argument'', a ``wait-and-see
argument'', a ``forcing argument'', etc. ]

However, it now appears that recursion theorists and at least some
theoretical computer scientists *do* want to refer to things like
to-do lists and multitasking operating systems as applications of
``priority methods''.  

Let's be clear about what is at stake here.  Priority methods are
certainly the most distinctive hallmark of ``pure'' recursion theory;
see e.g. Soare's 1987 monograph on recursively enumerable sets and
degrees.  The importance of priority methods in ``pure'' recursion
theory is unquestioned.  The question that we are now discussing is:

  What is the *importance* or *value* of ``pure'' recursion theory?
  What are its ``applications''?  In terms of the applications, how
  relevant are the distinctive concepts and methods of pure recursion
  theory, especially priority methods?

The organizers of the CTA meeting (``Computability Theory and
Applications'') implicitly raised this question in their manifesto
<http://www.ams.org/meetings/src-cholak.html>.  An ongoing discussion
of these issues is at <http://www.math.psu.edu/simpson/cta/>.

This was exactly my purpose in formulating the example of a to-do
list: to obtain clarification of Stuart Kurtz's contention (in Soare's
posting of 27 Jul 1999 14:03:43) that priority methods are routinely
used in programming practice.  It seems that the recursion theorists
are now defining the term ``priority method'' very broadly, in such a
way that Kurtz's contention becomes true or at least plausible.  They
evidently hope that this move will help to promote the importance of
recursion-theoretic concepts and methods.

-- Steve Simpson