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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2003, 6 (1), pp.133-142
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00958996
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 13 mars 2014 - 16:59:41
Dernière modification le : mercredi 29 novembre 2017 - 10:26:23
Document(s) archivé(s) le : vendredi 13 juin 2014 - 12:13:11

Fichier

dm060111.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

92

Téléchargements de fichiers

500