FOM: Priority arguments in complexity (also RFT in inductive inference)

[John Case]

My favorite priority arguments in complexity theory are in

   @inproceedings{        Kur-Mah-Roy:b:90:selman,
   editor =        "Selman, A.",
   author =        "Kurtz, S. and Mahaney, S. and Royer, J.",
   title =         "The Structure of Complete Degrees",
   booktitle =         "Complexity Theory Retrospective",
   pages =         "108--146",
   publisher =     "Springer-Verlag, NY",
   year =          1990}
   
   AND
   
   @article{   Che-Hom:m:98,
   author =        "Z. Chen and S. Homer",
   title =         "The Bounded Injury Priority Method and the Learnability of
                    Unions of Chains of Rectangles",
   note =        "Preprint at  
                  http://cs-www.bu.edu/faculty/homer/papers/apal.ps",
   year =          1998}

However, my own taste for RFT in complexity theory runs more toward fancy (and
computationally feasible) recursion theorems of the program self (and other)
reference type. (-8  See: 

   @book{          Roy-Cas:b:94,
   author =        "Royer, J. and Case, J.",
   title =         "Subrecursive Programming Systems: Complexity and 
                    Succinctness" ,
   series =         "Research monograph in
   Progress in Theoretical Computer Science" ,
   publisher =     "{Birkh\"auser}~Boston",
   year =          1994}
   
   AND
   
   @article{Cas:j:91,
           author =        "J. Case",
           year =          "{ 1991}",
           title =         "Effectivizing Inseparability",
           journal =       "Zeitschrift {f\"ur} Mathematische Logik und 
                            Grundlagen der Mathematik",
           volume=         37,
           pages =         "97-111"}

In \cite{Roy-Cas:b:94} we develop and use (\cite{Roy-Cas:b:94,Cas:j:91})
a Hybrid Recursion Theorem. This permits, for {\em example\/} self and other 
reference between a system for the multitape Turing machine programs 
explicitly clocked to halt in a quadratic in the length of their inputs and a 
system for the functions partial recursive in the halting problem.  In this 
way some of the subrecursively difficult combinatorics can be trivially handled 
in the latter system, a system where $Sigma_2^0$ requirements may be expressed, 
etc.  I suppose constructions with more complex requirements in the future 
might be handled with full blown priority arguments --- but in the super (not
the sub) recursive system. (-8  BTW, in the Hybrid Recursion Theorem examples, 
the subrecursive program(s) constructed can make some sense of the I/O behavior 
of their super recursive counterparts thanks to the result, generalizing Post
and others, that each function partial recursive in the halting problem is
uniformly the limit of a suitable linear-time computable function
\cite{Roy-Cas:b:94}.

John Case

PS: I note too that there have been and are now researchers (the so called
inductive inference community) within computational learning theory 
(researchers mostly in the US, Germany and Latvia, but with representation in 
at least Asia and Australia) who apply recursive function theory {\em methods}
in this area.  Many of these people are employed in computer science 
departments, but some are employed in mathematics or other departments.  
See:  the Appendix in Odifreddi's upcoming? second volume on RFT; the COLT, 
EuroCOLT, and ALT proceedings; and the first edition of Osherson, Stob and 
Weinstein's {\em Systems That Learn}, MIT Press, 1986.  The second edition, 
co-authored by Jain, S., Osherson, D., Royer, J., and Sharma, A., also with 
MIT Press, is to appear soon.  I note too that the CMU philospher, Kevin
Kelly, treats, among other things, this RFT approach to inductive inference in 
his {\em The Logic of Inquiry}, Oxford Press, 1996. (-8  JC