In computability theory, computational complexity theory and proof theory, the slow-growing hierarchy is an ordinal-indexed family of slowly increasing functions gα: N → N (where N is the set of natural numbers, {0, 1, ...}). It contrasts with the fast-growing hierarchy.
Let μ be a large countable ordinal such that a fundamental sequence is assigned to every limit ordinal less than μ. The slow-growing hierarchy of functions gα: N → N, for α < μ, is then defined as follows:[1]
Here α[n] denotes the nth element of the fundamental sequence assigned to the limit ordinal α.
The article on the Fast-growing hierarchy describes a standardized choice for fundamental sequence for all α < ε0.
The slow-growing hierarchy grows much more slowly than the fast-growing hierarchy. Even gε0 is only equivalent to f3 and gα only attains the growth of fε0 (the first function that Peano arithmetic cannot prove total in the hierarchy) when α is the Bachmann–Howard ordinal.[2][3][4]
However, Girard proved that the slow-growing hierarchy eventually catches up with the fast-growing one.[2] Specifically, that there exists an ordinal α such that for all integers n
where fα are the functions in the fast-growing hierarchy. He further showed that the first α, this holds for, is the ordinal of the theory ID<ω of arbitrary finite iterations of an inductive definition.[5] However, for the assignment of fundamental sequences found in [3] the first match up occurs at the level ε0.[6] For Buchholz style tree ordinals it could be shown that the first match up even occurs at .
Extensions of the result proved[5] to considerably larger ordinals show that there are very few ordinals below the ordinal of transfinitely iterated -comprehension where the slow- and fast-growing hierarchy match up.[7]
The slow-growing hierarchy depends extremely sensitively on the choice of the underlying fundamental sequences.[6][8][9]
Cichon provided an interesting connection between the slow-growing hierarchy and derivation length for term rewriting.[3][non-primary source needed]