Fast-growing hierarchy
Ordinal-indexed family of rapidly increasing functions: ℕ→ℕ / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Fast-growing hierarchy?
Summarize this article for a 10 year old
SHOW ALL QUESTIONS
In computability theory, computational complexity theory and proof theory, a fast-growing hierarchy (also called an extended Grzegorczyk hierarchy, or a Schwichtenberg-Wainer hierarchy)[1] 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.