Ordinal recursion, and a refinement of the extended Grzegorczyk hierarchy

DOI10.2307/2272973zbMath0261.02031OpenAlexW2167003332MaRDI QIDQ5676207

Stanley S. Wainer

Publication date: 1972

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2272973

Mathematics Subject Classification ID

Recursive functions and relations, subrecursive hierarchies (03D20) Recursively (computably) enumerable sets and degrees (03D25) Hierarchies of computability and definability (03D55)

Related Items

Majorizing provably recursive functions in fragments of PA, Investigations on slow versus fast growing: How to majorize slow growing functions nontrivially by fast growing ones, Slow growing versus fast growing, A Combinatorial Approach to Complexity Theory via Ordinal Hierarchies, Ordinal recursive bounds for Higman's theorem, A Short Proof of Two Recently Discovered Independence Results Using Recursion Theoretic Methods, Functorial Fast-Growing Hierarchies, Complexity of algorithms and computations, Type-theoretic approaches to ordinals, Minimal readability of intuitionistic arithmetic and elementary analysis, On mathematical instrumentalism, Some interesting connections between the slow growing hierarchy and the Ackermann function, Subsystems of true arithmetic and hierarchies of functions, Long finite sequences, Proof theory and ordinal analysis, Ackermann's substitution method (remixed), Unnamed Item, The Parametric Complexity of Lossy Counter Machines, The slow-growing and the Graegorczyk hierarchies, On definition trees of ordinal recursive functionals: Reduction of the recursion orders by means of type level raising, P.R.-Regulated Systems of Notation and the Subrecursive Hierarchy Equivalence Property

Cites Work

• Nested recursion
• Hierarchies of number-theoretic functions. I
• A classification of the ordinal recursive functions
• Eine Klassifikation der ε₀‐Rekursiven Funktionen