An application of results by Hardy, Ramanujan and Karamata to Ackermannian functions - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2003

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

Résumé

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.
Fichier principal
Vignette du fichier
dm060111.pdf (81.69 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00958996 , version 1 (13-03-2014)

Identifiants

Citer

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

Collections

TDS-MACS
134 Consultations
1127 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More