Fast-growing hierarchy

<p>In <a href="/facts/Computability_theory/cqDfXwdf">computability theory</a>, <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a> and <a href="/facts/Proof_theory/kopBdQn9">proof theory</a>, a fast-growing hierarchy (also called an extended <a href="/facts/Grzegorczyk_hierarchy/tUAxep2T">Grzegorczyk hierarchy</a>, or a Schwichtenberg-Wainer hierarchy) is an ordinal-indexed family of rapidly increasing functions <i>f</i>α: N → N (where N is the set of <a href="/facts/Natural_numbers/u65og8JE">natural numbers</a> {0, 1, ...}, and α ranges up to some large countable <a href="/facts/Ordinal_number/GelFLjJt">ordinal</a>). A primary example is the Wainer hierarchy, or Löb–Wainer hierarchy, which is an extension to all α < <a href="/facts/Epsilon_numbers_(mathematics)/t7w8KgA9">ε0</a>.  Such hierarchies provide a natural way to classify <a href="/facts/Computable_function/dzwBlLGn">computable functions</a> according to rate-of-growth and <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity</a>.
</p>

Fast-growing hierarchy open-in-new

Fast-growing hierarchy