6 found
Sort by:
  1. Geoffrey E. Ostrin & Stanley S. Wainer (2005). Elementary Arithmetic. Annals of Pure and Applied Logic 133 (1):275-292.
    There is a very simple way in which the safe/normal variable discipline of Bellantoni–Cook recursion [S. Bellantoni, S. Cook, A new recursion theoretic characterization of the polytime functions, Computational Complexity 2 97–110] can be imposed on arithmetical theories like PA: quantify over safes and induct on normals. This weakens the theory severely, so that the provably recursive functions become more realistically computable . Earlier results of D. Leivant [Intrinsic theories and computational complexity, in: D. Leivant , Logic and Computational Complexity, (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  2. Stanley S. Wainer & Richard S. Williams (2005). Inductive Definitions Over a Predicative Arithmetic. Annals of Pure and Applied Logic 136 (1-2):175-188.
    Girard’s maxim, that Peano Arithmetic is a theory of one inductive definition, is re-examined in the light of a weak theory EA formalising basic principles of Nelson’s predicative Arithmetic.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  3. Stanley S. Wainer (1999). Accessible Recursive Functions. Bulletin of Symbolic Logic 5 (3):367-388.
    The class of all recursive functions fails to possess a natural hierarchical structure, generated predicatively from "within". On the other hand, many (proof-theoretically significant) sub-recursive classes do. This paper attempts to measure the limit of predicative generation in this context, by classifying and characterizing those (predictably terminating) recursive functions which can be successively defined according to an autonomy condition of the form: allow recursions only over well-orderings which have already been "coded" at previous levels. The question is: how can a (...)
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  4. Stanley S. Wainer (1998). Hierarchies of Provably Recursive Functions. In Samuel R. Buss (ed.), Bulletin of Symbolic Logic. Elsevier 149.
  5. Wilfried Sieg & Stanley S. Wainer, Program Transformation and Proof Transformation.
    Wilfred Sieg and Stanley S. Wainer. Program Transformation and Proof Transformation.
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  6. Douglas Cenzer, Peter Clote, Rick L. Smith, Robert I. Soare & Stanley S. Wainer (1986). Members of Countable Π10 Classes. Annals of Pure and Applied Logic 31 (2):145-163.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation