Ordinal complexity of recursive definitions

DOI10.1016/0890-5401(92)90027-DzbMath0768.03027OpenAlexW1980915530MaRDI QIDQ1193596

M. V. H. Fairtlough, Stanley S. Wainer

Publication date: 27 September 1992

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(92)90027-d

zbMATH Keywords

hierarchyHardy functionalsnested recursionsrecursive and iterative definitions of total computable functionsstructured tree-ordinalssubrecursion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items (7)

Investigations on slow versus fast growing: How to majorize slow growing functions nontrivially by fast growing ones ⋮ Transfinite induction within Peano arithmetic ⋮ Ordinal recursive bounds for Higman's theorem ⋮ The hierarchy of terminating recursive programs over N ⋮ Complexity Hierarchies beyond Elementary ⋮ Partitioning 𝛼–large sets: Some lower bounds ⋮ An ordinal calculus for proving termination in term rewriting

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nested recursion
• Rapidly growing Ramsey functions
• Slow growing versus fast growing
• A Short Proof of Two Recently Discovered Independence Results Using Recursion Theoretic Methods

This page was built for publication: Ordinal complexity of recursive definitions