The Ackermann functions are not optimal, but by how much?

Journal of Symbolic Logic 75 (1):289-313 (2010)
  Copy   BIBTEX

Abstract

By taking a closer look at the construction of an Ackermann function we see that between any primitive recursive degree and its Ackermann modification there is a dense chain of primitive recursive degrees

Categories

Keywords

Reprint years

DOI

10.2178/jsl/1264433922

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 103,401

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Some Hierarchies of Primitive Recursive Functions on Term Algebras.Klaus-Hilmar Sprenger - 1997 - Mathematical Logic Quarterly 43 (2):251-286.
Classifying the phase transition threshold for Ackermannian functions.Eran Omri & Andreas Weiermann - 2009 - Annals of Pure and Applied Logic 158 (3):156-162.
Unary primitive recursive functions.Daniel E. Severin - 2008 - Journal of Symbolic Logic 73 (4):1122-1138.
Some Interesting Connections between the Slow Growing Hierarchy and the Ackermann Function.Andreas Weiermann - 2001 - Journal of Symbolic Logic 66 (2):609-628.
Enhancing induction in a contraction free logic with unrestricted abstraction: from $$\mathbf {Z}$$ Z to $$\mathbf {Z}_2$$ Z 2.Uwe Petersen - forthcoming - Archive for Mathematical Logic:1-45.
Non-definability of the Ackermann function with type 1 partial primitive recursion.Karl-Heinz Niggl - 1997 - Archive for Mathematical Logic 37 (1):1-13.
The Nonarithmeticity of the Predicate Logic of Strictly Primitive Recursive Realizability.Valery Plisko - forthcoming - Review of Symbolic Logic:1-30.
On primitive recursive permutations and their inverses.Frank B. Cannonito & Mark Finkelstein - 1969 - Journal of Symbolic Logic 34 (4):634-638.
Primitive Recursive Functions.Raphael M. Robinson - 1948 - Journal of Symbolic Logic 13 (2):113-114.
On a Subrecursive Hierarchy and Primitive Recursive Degrees.Paul Axt - 1960 - Journal of Symbolic Logic 25 (2):167-168.

Analytics

Added to PP
2010-09-12

Downloads
53 (#427,749)

6 months
10 (#281,857)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Proof lengths for instances of the Paris–Harrington principle.Anton Freund - 2017 - Annals of Pure and Applied Logic 168 (7):1361-1382.

Add more citations

References found in this work

Subrecursion: functions and hierarchies.H. E. Rose - 1984 - New York: Oxford University Press.
Hierarchies of number-theoretic functions. I.M. H. Löb & S. S. Wainer - 1970 - Archive for Mathematical Logic 13 (1-2):39-51.
Hierarchies of number-theoretic functions II.M. H. Löb & S. S. Wainer - 1970 - Archive for Mathematical Logic 13 (3-4):97-113.

Add more references