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

https://hal.inria.fr/hal-00958996
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
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

File

dm060111.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00958996, version 1

Collections

Citation

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

Share

Metrics

Record views

284

Files downloads

1706