Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T01:02:54.539Z Has data issue: false hasContentIssue false

An extremely sharp phase transition threshold for the slow growing hierarchy

Published online by Cambridge University Press:  11 October 2006

ANDREAS WEIERMANN
Affiliation:
Fakulteit Bètawetenschappen, Departement Wiskunde, Postbox 80010, 3508 TA Utrecht, The Netherlands Email: weierman@math.uu.nl
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We investigate natural systems of fundamental sequences for ordinals below the Howard–Bachmann ordinal and study growth rates of the resulting slow growing hierarchies. We consider a specific assignment of fundamental sequences that depends on a non-negative real number $\varepsilon$. We show that the resulting slow growing hierarchy is eventually dominated by a fixed elementary recursive function if $\varepsilon$ is equal to zero. We show further that the resulting slow growing hierarchy exhausts the provably recursive functions of $\sfb{ID}_1$ if $\varepsilon$ is strictly greater than zero. Finally, we show that the resulting fast growing hierarchies exhaust the provably recursive functions of $\sfb{ID}_1$ for all non-negative values of $\varepsilon$. Our result is somewhat surprising since usually the slow growing hierarchy along the Howard–Bachmann ordinal exhausts precisely the provably recursive functions of $\sfb{PA}$. Note that the elementary functions are a very small subclass of the provably recursive functions of $\sfb{PA}$, and the provably recursive functions of $\sfb{PA}$ are a very small subclass of the provably recursive functions of $\sfb{ID}_1$. Thus the jump from $\varepsilon$ equal to zero to $\varepsilon$ greater than zero is one of the biggest jumps in growth rates for subrecursive hierarchies one might think of.

Information

Type
Paper
Copyright
2006 Cambridge University Press