The intrinsic difficulty of recursive functions

DOI10.1007/BF00372775MaRDI QIDQ1919986zbMATH OpenFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 3885307
• On the intrinsic complexity of learning recursive functions
• A note on arbitrarily complex recursive functions
• On a complexity-based way of constructivizing the recursive functions
• scientific article; zbMATH DE number 2013793

Cites work

• scientific article; zbMATH DE number 991288 (Why is no real title available?)
• scientific article; zbMATH DE number 3654098 (Why is no real title available?)
• scientific article; zbMATH DE number 43713 (Why is no real title available?)
• scientific article; zbMATH DE number 1142308 (Why is no real title available?)
• scientific article; zbMATH DE number 1142309 (Why is no real title available?)
• scientific article; zbMATH DE number 1142310 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3083488 (Why is no real title available?)
• A Classification of the Recursive Functions
• A Hierarchy of Primitive Recursive Functions
• A Machine-Independent Theory of the Complexity of Recursive Functions
• A characterization of the power of vector machines
• An Overview of the Theory of Computational Complexity
• Classes of Predictably Computable Functions
• Classifications of Recursive Functions by Means of Hierarchies
• Classifying the computational complexity of problems
• Hierarchies of number-theoretic functions. I
• Machine Dependence of Degrees of Difficulty
• On a complexity-based way of constructivizing the recursive functions
• Ordinal Hierarchies and Naming Complexity Classes
• The slow-growing and the Graegorczyk hierarchies
• Theories of computational complexity
• ``Natural properties of flowchart step-counting measures

Cited in

(3)

• scientific article; zbMATH DE number 3885307 (Why is no real title available?)
• Tailoring recursion for complexity
• Multigrade extension of relational grammar

This page was built for publication: The intrinsic difficulty of recursive functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1919986)