Fast-Growing Hierarchy

A Fast-Growing Hierarchy (FGH) is an ordinal-indexed hierarchy of functions satisfying certain restrictions. FGHs are used for assigning growth rates to fast computable functions, and are useful for approximating scores and halting times of Turing machines.

Definition

Given a system of fundamental sequences for limit ordinals below $\lambda$, its corresponding FGH is defined by

$${\begin{array}{l}f_{0}(n)&=&n+1\\f_{\alpha +1}(n)&=&f_{\alpha }^{n}(n)&{\text{for }}\alpha <\lambda \\f_{\alpha }(n)&=&f_{\alpha [n]}(n)&{\text{for limit ordinals }}\alpha <\lambda \end{array}}$$

Most natural fundamental sequence systems almost exactly agree on the growth rates in their corresponding FGHs. Specifically, if $f,f'$ are FGHs given by natural fundamental sequence systems, it is usually the case that $f_{\alpha }(n+1)>f'_{\alpha }(n)$ and $f'_{\alpha }(n+1)>f_{\alpha }(n)$ for all natural $n$ and all successor ordinals $\alpha$. For this reason, the specific choice of a fundamental sequence system often doesn't matter for large ordinals. For small ordinals (below $\varepsilon _{0}$), a common choice of fundamental sequences is given by

$${\begin{array}{l}(\alpha +\omega ^{\beta +1})[n]&=&\alpha +\omega ^{\beta }n&{\text{if }}\alpha {\text{ is a multiple of }}\omega ^{\beta +1}\\(\alpha +\omega ^{\beta })[n]&=&\alpha +\omega ^{\beta [n]}&{\text{if }}\alpha {\text{ is a multiple of }}\omega ^{\beta }{\text{ and }}\beta {\text{ is a limit ordinal}}\end{array}}$$

The FGH given by these fundamental sequences is sometimes called the Wainer hierarchy. Above $\varepsilon _{0}$, a relatively elegant choice is the expansion associated to the Bashicu matrix system, which has the Bachmann property.