FOM: priority arguments in applied recursion theory
Stephen G Simpson
simpson at math.psu.edu
Tue Aug 3 14:15:14 EDT 1999
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
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
More information about the FOM