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)
Full work available at URL: https://doi.org/10.1016/0890-5401(92)90027-d
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
An ordinal calculus for proving termination in term rewriting, The hierarchy of terminating recursive programs over N, 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