[Date Index] [Thread Index] [FOM Postings] [FOM Home]

*To*: fom@math.psu.edu*Subject*: FOM: priority arguments in applied recursion theory*From*: Stephen G Simpson <simpson@math.psu.edu>*Date*: Wed, 28 Jul 1999 15:12:36 -0400 (EDT)*Cc*: stuart@cs.uchicago.edu*In-Reply-To*: <19990727190343.BB06C15381F@sherman.cs.uchicago.edu>*Organization*: Department of Mathematics, Pennsylvania State University*References*: <19990727190343.BB06C15381F@sherman.cs.uchicago.edu>*Reply-To*: simpson@math.psu.edu*Sender*: owner-fom@math.psu.edu

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/

**Follow-Ups**:**Steve Stevenson**- FOM: priority arguments in applied recursion theory

**References**:**Robert I. Soare**- No Subject

[Date Prev] [Date Next] [Thread Prev] [Thread Next]

[Date Index] [Thread Index] [FOM Postings] [FOM Home]