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

dmtcs:339 - Discrete Mathematics & Theoretical Computer Science, January 1, 2003, Vol. 6 no. 1 - https://doi.org/10.46298/dmtcs.339
An application of results by Hardy, Ramanujan and Karamata to Ackermannian functions

Authors: Andreas Weiermann

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.


Volume: Vol. 6 no. 1
Published on: January 1, 2003
Imported on: March 26, 2015
Keywords: Ackermann function,Karamata's theorem,Hardy Ramanujan methods,analytic combinatorics,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Consultation statistics

This page has been seen 203 times.
This article's PDF has been downloaded 532 times.