Some interesting connections between the slow growing hierarchy and the Ackermann function

E-ISSN： 1943-5886|66|2|609-628

ISSN： 0022-4812

Source： The Journal of Symbolic Logic, Vol.66, Iss.2, 2001-06, pp. : 609-628

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

It is shown that the so called slow growing hierarchy depends non trivially on the choice of its underlying structure of ordinals. To this end we investigate the growth rate behaviour of the slow growing hierarchy along natural subsets of notations for Γ₀. Let T be the set-theoretic ordinal notation system for Γ₀ and T^tree the tree ordinal representation for Γ₀. It is shown in this paper that (G_α )_α∈T matches up with the class of functions which are elementary recursive in the Ackermann function as does (by folklore). By thinning out terms in which the addition function symbol occurs we single out subsystems T* ⊆ T and T ^tree* ⊆ T^tree (both of order type not exceeding ε ₀) and prove that still matches up with but now consists of elementary recursive functions only. We discuss the relationship between these results and the Γ₀-based termination proof for the standard rewrite system for the Ackermann function.