Skip to Main content Skip to Navigation
Journal articles

An application of results by Hardy, Ramanujan and Karamata to Ackermannian functions

Abstract : The Ackermann function is a fascinating and well studied paradigm for a function which eventually dominates all primitive recursive functions. By a classical result from the theory of recursive functions it is known that the Ackermann function can be defined by an unnested or descent recursion along the segment of ordinals below ω ^ω (or equivalently along the order type of the polynomials under eventual domination). In this article we give a fine structure analysis of such a Ackermann type descent recursion in the case that the ordinals below ω ^ω are represented via a Hardy Ramanujan style coding. This paper combines number-theoretic results by Hardy and Ramanujan, Karamata's celebrated Tauberian theorem and techniques from the theory of computability in a perhaps surprising way.
Document type :
Journal articles
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Thursday, March 13, 2014 - 4:59:41 PM
Last modification on : Tuesday, August 13, 2019 - 10:16:02 AM
Long-term archiving on: : Friday, June 13, 2014 - 12:13:11 PM


Files produced by the author(s)




Andreas Weiermann. An application of results by Hardy, Ramanujan and Karamata to Ackermannian functions. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2003, Vol. 6 no. 1 (1), pp.133-142. ⟨10.46298/dmtcs.339⟩. ⟨hal-00958996⟩



Record views


Files downloads