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

DOI10.2307/2695032zbMATH Open0993.03074OpenAlexW2120653720MaRDI QIDQ2747706FDOQ2747706

Andreas Weiermann

Publication date: 16 September 2002

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

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

zbMATH Keywords

computational complexityterm rewritingAckermann functionordinal notation systemsCichon's principlelengths of derivationsslow growing hierarchiestree ordinalsVeblen functions

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• Bounding derivation lengths with functions from the slow growing hierarchy
• Goodstein sequences for prominent ordinals up to the Bachmann-Howard ordinal
• Title not available (Why is that?)
• Title not available (Why is that?)
• Predicatively unprovable termination of the Ackermannian Goodstein process

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2747706)