Ordinal complexity of recursive definitions
From MaRDI portal
Publication:1193596
DOI10.1016/0890-5401(92)90027-DzbMath0768.03027MaRDI QIDQ1193596
M. V. H. Fairtlough, Stanley S. Wainer
Publication date: 27 September 1992
Published in: Information and Computation (Search for Journal in Brave)
hierarchy; Hardy functionals; nested recursions; recursive and iterative definitions of total computable functions; structured tree-ordinals; subrecursion
68Q25: Analysis of algorithms and problem complexity
03D15: Complexity of computation (including implicit computational complexity)
03D20: Recursive functions and relations, subrecursive hierarchies
Related Items
Ordinal recursive bounds for Higman's theorem, Investigations on slow versus fast growing: How to majorize slow growing functions nontrivially by fast growing ones, Transfinite induction within Peano arithmetic, Complexity Hierarchies beyond Elementary, Partitioning 𝛼–large sets: Some lower bounds
Cites Work