The intrinsic difficulty of recursive functions

DOI10.1007/BF00372775zbMath0862.03024MaRDI QIDQ1919986

F. W. Kroon

Publication date: 28 July 1996

Published in: Studia Logica (Search for Journal in Brave)

zbMATH Keywords

subrecursive hierarchiescomplexity of recursive functionsintrinsic natural complexity measure

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items

Multigrade extension of relational grammar

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On a complexity-based way of constructivizing the recursive functions
• Theories of computational complexity
• A characterization of the power of vector machines
• ``Natural properties of flowchart step-counting measures
• Classifications of Recursive Functions by Means of Hierarchies
• Classes of Predictably Computable Functions
• The slow-growing and the Graegorczyk hierarchies
• Classifying the computational complexity of problems
• Ordinal Hierarchies and Naming Complexity Classes
• Machine Dependence of Degrees of Difficulty
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Hierarchies of number-theoretic functions. I
• An Overview of the Theory of Computational Complexity
• A Classification of the Recursive Functions
• A Hierarchy of Primitive Recursive Functions