Classifying the phase transition threshold for Ackermannian functions

Classifying the phase transition threshold for Ackermannian function. (2009)

Eran Omri, Andreas Weiermann.

Journal of Annals of Pure and Applied Logic, 158(3):156 – 162.

Abstract

It is well known that the Ackermann function can be defined via diagonalization from an iteration hierarchy (of Grzegorczyk type) which is built on a start function like the successor function. In this paper we study for a given start function g iteration hierarchies with a sub-linear modulus h of iteration. In terms of g and h we classify the phase transition for the resulting diagonal function from being primitive recursive to being Ackermannian.