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}{lll}{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^{\prime }$ are FGHs given by natural fundamental sequence systems, it is usually the case that $f_{\alpha }(n+1)>f{\text{'}}_{\alpha }(n)$ and $f{\text{'}}_{\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 ${\epsilon }_0$), a common choice of fundamental sequences is given by

$$\begin{array}{llll}(\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 ${\epsilon }_0$, a relatively elegant choice is the expansion associated to the Bashicu matrix system, which has the Bachmann property.

Growth Bound Theorem

The Fast-Growing Hierarchy Growth Bound Theorem is an important result in mathematical logic that has significant implications for unprovability results. The theorem highlights a relationship between computable functions that are provably total in first-order Peano Arithmetic (PA) and the fast-growing functions in the Wainer hierarchy.

The theorem is based on work by several mathematicians. Georg Kreisel laid the groundwork in 1952 by investigating connections between recursions over well ordered sets and proofs in PA. These results were subsequently extended by many others; the following form is based on the presentation by Buchholz and Wainer.

Statement

Let $T$ be a Turing machine that computes a function $g:\mathbb{\mathbb{N}}\to \mathbb{\mathbb{N}}$, terminating on every input. Suppose that PA can prove the statement «$T$ terminates on every input.» Then $g$ cannot grow too fast: There exist $\alpha <{\epsilon }_0$ and $n_0\in \mathbb{\mathbb{N}}$ such that $g(n)<F_{\alpha }(n)$ for every $n\ge n_0$.

References

Wilfried Buchholz and Stan S. Wainer. Provably computable functions and the fast growing hierarchy. In S. G. Simpson, editor, Logic and Combinatorics, volume 65 of Contemporary Mathematics, pages 179–198. AMS, 1987. [1]