Fast-growing hierarchy

In computability theory, computational complexity theory and proof theory, the fast-growing hierarchy (also called the Wainer hierarchy and the extended Grzegorczyk hierarchy) is a certain ordinal-indexed family of rapidly increasing functions f_α: ω → ω (where ω is the least infinite ordinal). This hierarchy provides a natural way to classify computable functions according to rate-of-growth and computational complexity.

Definition

Let μ be a large countable ordinal such that a fundamental sequence is assigned to every limit ordinal less than μ. The fast-growing hierarchy of functions f_α: ω → ω, for α < μ, is then defined as follows:

f0(n) = n + 1,

fα+1(n) = fαn(n),  


fα(n) = fα[n](n) if α is a limit ordinal.

Here f_αⁿ(n) = f_α(f_α(...(f_α(n))...)) denotes the n^th iterate of f_α applied to n, and α[n] denotes the n^th element of the fundamental sequence assigned to the limit ordinal α. (A common alternative definition takes the number of iterations to be n+1, rather than n, in the second line above.)

The fundamental sequences assigned to limit ordinals λ ≤ ε₀ are defined as follows:

• if λ = α + β, then λ[n] = α + β[n],

• if λ = ω^α+1, then λ[n] = ω^αn,

• if λ = ω^α for a limit ordinal α, then λ[n] = ω^α[n],

• if λ = ε₀, then λ[0] = 0 and λ[n + 1] = ω^λ[n].

The definition becomes more complicated for limit ordinals greater than ε₀, although it can be extended to ordinals well beyond the Γ₀.

Points of Interest

Following are some relevant points of interest about the fast-growing hierarchy {f_α| α < μ}:

• Every f_α is a total computable function.

• If α < β, then f_α is dominated by f_β. (For any two functions f, g: ω → ω, f is said to dominate g if f(n) > g(n) for all sufficiently large n.)

• Every primitive recursive function is dominated by some f_α with α < ω. Hence every primitive recursive function is dominated by f_ω, which is a variant of the Ackermann function.

• If α < ε₀, then f_α is computable and provably total in Peano Arithmetic.

• Every computable function that's provably total in Peano Arithmetic is dominated by some f_α with α < ε₀. Hence f_ε0 is not provably total in Peano Arithmetic.

• Goodstein's function (the length of the Goodstein sequence for a given argument) has the same rate-of-growth as f_ε0, and hence is not provably total in Peano Arithmetic.

• If α < β < ε₀, then f_α dominates every computable function within time and space bounded by some fixed iterate f_β^k.

• Friedman's TREE function dominates f _Γ0.

References

• Buchholz, W., and Wainer, S.S. Provably Computable Functions and the Fast Growing Hierarchy. Logic and Combinatorics, edited by S. Simpson, Comtemporary Mathematics, Vol. 65, AMS (1987), 179-198.

• Cichon, E.A., and Wainer, S.S. The Slow-Growing and the Grzegorczyk Hierarchies. J. of Symbolic Logic 48(2) (1983), 399-408.

• Gallier, Jean H. (1991), "What's so special about Kruskal's theorem and the ordinal Γ₀? A survey of some results in proof theory", Ann. Pure Appl. Logic, 53 (3): 199–260, doi:10.1016/0168-0072(91)90022-E, MR1129778 PDF's: part 1 2 3.

• M.H. Lob and S.S. Wainer, Hierarchies of number theoretic functions, Arch. Math. Logik, 13, 1970. Correction, Arch. Math. Logik, 14, 1971.

• Wainer, S.S. Slow Growing Versus Fast Growing. J. of Symbolic Logic 54(2) (1989), 608-614.