Some interesting connections between the slow growing hierarchy and the Ackermann function

DOI10.2307/2695032zbMath0993.03074OpenAlexW2120653720MaRDI QIDQ2747706

Andreas Weiermann

Publication date: 16 September 2002

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

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

zbMATH Keywords

computational complexityterm rewritinglengths of derivationsAckermann functionordinal notation systemsCichon's principleslow growing hierarchiestree ordinalsVeblen functions

Mathematics Subject Classification ID

Recursive functions and relations, subrecursive hierarchies (03D20) Recursive ordinals and ordinal notations (03F15)

Related Items (2)

Goodstein sequences for prominent ordinals up to the Bachmann-Howard ordinal ⋮ Predicatively unprovable termination of the Ackermannian Goodstein process

Cites Work

• Termination proofs for term rewriting systems by lexicographic path orderings imply multiply recursive derivation lengths
• A slow growing analogue to Buchholz' proof
• Some results on cut-elimination, provable well-orderings, induction and reflection
• Proof-theoretic analysis of termination proofs
• The slow-growing and the Graegorczyk hierarchies
• Ausgezeichnete Folgen Für Prädikative Ordinalzahlen und Prädikativ‐Rekursive Funktionen
• Π12-logic, Part 1: Dilators
• A Uniform Approach to Fundamental Sequences and Hierarchies
• Systems of predicative analysis, II: Representations of ordinals
• Ordinal recursion, and a refinement of the extended Grzegorczyk hierarchy

This page was built for publication: Some interesting connections between the slow growing hierarchy and the Ackermann function