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

A fundamental sequence for an ordinal $\alpha$ is an increasing sequence of ordinals $<\alpha$ which is unbounded in $\alpha$. The $\beta$-th element of $\alpha$'s fundamental sequence is denoted by $\alpha [\beta ]$. In the context of FGHs, there is usually a restriction that the sequence's length must be as small as possible (that is, the length is the cofinality of $\alpha$). A system of fundamental sequences for a set of ordinals is a function which assigns a fundamental sequence to each ordinal in the set.

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.