Fast-growing hierarchy

Common card · No. 336580

In computability theory, computational complexity theory and proof theory, a fast-growing hierarchy (also called an extended Grzegorczyk hierarchy, or a Schwichtenberg–Wainer hierarchy) is an ordinal-indexed family of rapidly increasing functions fα: N → N (where N is the set of natural numbers {0, 1, ...}, and α ranges up to some large countable ordinal). A primary example is the Wainer hierarchy, or Löb–Wainer hierarchy, which is an extension to all α < ε0. Such hierarchies provide a natural way to classify computable functions according to rate-of-growth and computational complexity.

Read on Wikipedia