[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*: Tue, 27 Jul 1999 16:15:06 -0400 (EDT)*Cc*: fenner@cs.sc.edu, Rod.Downey@MCS.VUW.AC.NZ*In-Reply-To*: <Pine.BSF.3.96.990726161317.11728G-100000@phlox.cs.sc.edu>*Organization*: Department of Mathematics, Pennsylvania State University*References*: <14231.47146.661199.79846@mordred.cs.utk.edu><Pine.BSF.3.96.990726161317.11728G-100000@phlox.cs.sc.edu>*Reply-To*: simpson@math.psu.edu*Sender*: owner-fom@math.psu.edu

This posting is a contribution to the ongoing discussion of ``Simpson's Thesis''. Apparently most recursion theorists are not willing to discuss this and similar issues in public electronic forums such as FOM. But Downey and Fenner are notable exceptions. I thank them, and I hope we can continue the discussion. Fenner 26 Jul 1999 16:44:06 pointed to a Fenner/Kurtz/Royer paper, ``Every polynomial-time 1-degree collapses iff P = PSPACE.'' I downloaded the paper and had a look at it. The proof of the main theorem uses a technical lemma which is proved in an appendix. I'm willing to take Fenner's word that that proof is a priority argument. So, there is at least one priority argument in theoretical computer science. A counterexample to ``Simpson's Thesis''! Now, it seems to me the next question is: How prevalent are priority arguments in this area? I assume Fenner concurs with my remark that there are no priority arguments in the standard textbooks. But he also says: > Theoretical computer science is an area where the ratio of papers > to books is still pretty high. Fair enough. But then, 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? Contrast this to the ``pure'' theory of r.e. sets and Turing degrees, where almost every paper uses priority arguments. It is also relevant to ask whether the priority arguments can be eliminated, and what are the costs and benefits of eliminating them. Fenner points to a priority argument used to construct an oracle in computational complexity theory, where the priority argument was eventually eliminated. But Fenner says: > the original priority argument has great heuristic value. Could somebody please elaborate on this remark? The remark seems surprising, because in the example that Fenner points to, the result proved *without* a priority argument was considerably better, in that a recursive oracle was obtained. See <http://www.cs.sc.edu/~fenner/papers/nexp.PS>. A final remark: In this whole discussion of ``Simpson's Thesis'', we should try not to lose sight of the forest for the trees. ``Simpson's Thesis'' arose as part of a much larger issue, which has been implicitly raised by the CTA organizers in <http://www.ams.org/meetings/src-cholak.html>: What is ``applied recursion theory''? Moreover, as I argued in my FOM posting of 15 Jul 1999 22:33:53, the pure/applied dichotomy probably does more harm than good. A better way to frame the discussion may be: What is recursion theory? What are the issues and programs in recursion theory that are most meaningful for f.o.m.? -- Steve

**References**:**Stephen G Simpson**- FOM: priority arguments in applied recursion theory**Stephen Fenner**- Re: FOM: priority arguments in applied recursion theory

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

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