Switch to: References

Add citations

You must login to add citations.
  1. The intrinsic difficulty of recursive functions.F. W. Kroon - 1996 - Studia Logica 56 (3):427 - 454.
    This paper deals with a philosophical question that arises within the theory of computational complexity: how to understand the notion of INTRINSIC complexity or difficulty, as opposed to notions of difficulty that depend on the particular computational model used. The paper uses ideas from Blum's abstract approach to complexity theory to develop an extensional approach to this question. Among other things, it shows how such an approach gives detailed confirmation of the view that subrecursive hierarchies tend to rank functions in (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • On a complexity-based way of constructivizing the recursive functions.F. W. Kroon & W. A. Burkhard - 1990 - Studia Logica 49 (1):133 - 149.
    Let g E(m, n)=o mean that n is the Gödel-number of the shortest derivation from E of an equation of the form (m)=k. Hao Wang suggests that the condition for general recursiveness mn(g E(m, n)=o) can be proved constructively if one can find a speedfunction s s, with s(m) bounding the number of steps for getting a value of (m), such that mn s(m) s.t. g E(m, n)=o. This idea, he thinks, yields a constructivist notion of an effectively computable function, (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Elementary Functions and LOOP Programs.Zlatan Damnjanovic - 1994 - Notre Dame Journal of Formal Logic 35 (4):496-522.
    We study a hierarchy of Kalmàr elementary functions on integers based on a classification of LOOP programs of limited complexity, namely those in which the depth of nestings of LOOP commands does not exceed two. It is proved that -place functions in can be enumerated by a single function in , and that the resulting hierarchy of elementary predicates (i.e., functions with 0,1-values) is proper in that there are predicates that are not in . Along the way the rudimentary predicates (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • The Equivalence of Different Hierarchies of Elementary Functions.G. T. Herman - 1971 - Mathematical Logic Quarterly 17 (1):219-224.
    Download  
     
    Export citation  
     
    Bookmark   1 citation