FOM: priority arguments in applied recursion theory

[Stephen G Simpson]

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