# Hierarquia de crescimento rápido

Em Teoria da Computabilidade, Complexidade (informática) e Teoria da Prova, uma hierarquia de crescimento rápido (também chamado de hierarquia de Grzegorczyk estendida) é uma família indexada de funções que crescem rapidamente f$_α$: N → N (onde N é o conjunto dos números naturais {0, 1, 2, ...}) e α refere-se a algum número ordinal alto e contável. Um exemplo primário é a hierarquia de Wainer, ou a hierarquia de Löb-Wainer, que trata-se de uma extensão para todo α < ε$_0$. Tais hierarquias permitem uma classificação natural de funções computáveis, de acordo com a taxa-de-crescimento e a complexidade computacional.

## Definição

Seja μ um ordinal contável alto, tal que uma sequência fundamental (uma seqüência estritamente crescente de ordinais cujo supremo é o ordinal limite) é atribuída a cada ordinal limite menor que μ. Uma hierarquia de rápido crescimento de funções f$_α$: N → N, para α < μ, é definida da seguinte forma:
* $f_{0}(n)=n+1,\,$
* $f_{\alpha +1}(n)=f_{\alpha }^{n}(n),\,$
* $f_{\alpha }(n)=f_{\alpha [n]}(n)\,\!$ se α é o ordinal limite.
Aqui f$_α$$^n$(n) = f$_α$(f$_α$(...(f$_α$(n))...)) denota a n-ésima iteração de f$_α$ aplicada a “n”, e a α[n] denota o n-ésimo elemento da sequência fundamental definida pelo ordinal limite α. (Uma definição alternativa considera o número de iterações sendo “n”+1, em vez de “n”, na segunda linha acima).
A parte inicial desta hierarquia, que compreende as funções f$_α$ com indexação finita (por exemplo, a< ω), é normalmente chamada de hierarquia de Grzegorczyk, por conta da forte relação com a Hierarquia de Grzegorczyk . Porém, enquanto a primeira trata-se de uma família indexada de funções f$_n$, a segunda compreende uma família indexada de “conjuntos” de funções ${\mathcal {E}}^{n}$.
Generalizando ainda mais a definição acima, a hierarquia de rápida iteração é obtida fazendo com que f$_0$ para qualquer função crescente g: N → N.
Para ordinais limite não maiores que ε$_0$ (números que não são atingíveis a partir de 0, partindo de um número finito de passos), há uma definição natural direta para as sequências fundamentais (ver a Hierarquia de Wainer abaixo), mas além do ε$_0$, a definição é muito mais complicada. Porém, isso é possível para além do ordinal de Feferman–Schütte Γ$_0$, até o Ordinal de Bachmann-Howard. Usando funções psi de Buchholz, pode-se estender esta definição com facilidade a ordinais transfinitos.
Uma extensão totalmente especificada além do ordinais recursivos, acredita-se ser improvável, como justificada por Prӧmel et al. [1991](p. 348). Note que, em tal tentativa, surgiriam até problemas na notação ordinal.

## Hierarquia de Wainer

A Hierarquia de Wainer é a hierarquia de crescimento particular de funções f$_α$ (α ≤ ε$_0$) obtido através da definição das sequências fundamentais da seguinte forma [Gallier 1991][Prӧmel, et al, 1991.]: Para ordinais limite λ < ε$_0$, escrita na Forma Normal de Cantor :
* se λ = ω$^{α1}$ + ... + ω$^{αk−1}$ + ω$^{αk}$ for α$_1$ ≥ ... ≥ α$_{k−1}$ ≥ α$_k$, então λ[n] = ω$^{α1}$ + ... + ω$^{αk−1}$ + ω$^{αk}$[n],
* se λ = ω$^{α+1}$, então λ[n] = ω$^α$n,
* se λ = ω$^α$ para o ordinal limite α, então λ[n] = ω$^{α[n]}$,
e
* se λ = ε$_0$, pegue λ[0] = 0 e λ[n + 1] = ω$^{λ[n]}$ como em [Gallier 1991]; alternativamente, pegue a mesma sequência, começando com λ[0] = 1 como em [Prӧmel, et al., 1991]. Para n > 0, a versão alternativa possui um ω adicional na exponencial resultante. Por exemplo λ[n] = ω$^{ω...ω}$ com n omegas.
Alguns autores usam definições ligeiramente diferentes (ω$^{α+1}$[n] = ω$^α$(n+1), em vez de ω$^α$n), e alguns definem essa hierarquia apenas para α < ε$_0$ (excluindo f$_{ε0}$ da hierarquia).
Para ir além do ε$_0$, ver Sequências fundamentais para a hierarquia de Veblen.

## Pontos de Interesse

Adiante estão alguns pontos relevantes sobre o interesse em hierarquias de rápido crescimento:
* Toda f$_α$ é uma função total. Se as sequências fundamentais são computáveis, (como na Hierarquia de Wainer), então toda f$_α$ é uma função computável total.
* Na hierarquia de Wainer, f$_α$ é dominada por f$_β$ se α < β. (Para duas funções quaisquer f, g: N → N, diz-se que f domina g se f(n) > g(n) para todo n.)
* Na hierarquia de Grzegorczyk, toda função primitiva recursiva é dominada por algum f$_α$ com α < ω. Já na hierarquia de Wainer, toda função primitiva recursiva é dominada por f$_ω$, que é uma variante da função de Ackermann.
* Na hierarquia de Wainer, toda f$_α$ com α < ε$_0$ é computável e demonstravelmente total na Aritmética de Peano.
* Toda função computável que é provadamente total na Aritmética de Peano é dominada por algum f$_α$ com α < ε$_0$ na hierarquia de Wainer. Portanto, f$_{ε0}$ na hierarquia de Wainer não é provadamente total na Aritmética de Peano.
* A função de Goodstein tem aproximadamente a mesma taxa de crescimento de f$_{ε0}$ na hierarquia de Wainer, dominando toda f$_α$ em que α < $_0$, e, portanto, não é comprovadamente total na Aritmética Peano.
* Na hierarquia de Wainer, se α < β < ε$_0$, então f$_β$ domina toda função computável dentro dos limites de tempo e espaço das iterações de f$_α$$^k$.
* A hierarquia de Wainer de funções f$_α$ e a hierarquia de Hardy de funções h$_α$ são relacionadas por f$_α$ = h$_{ωα}$ para todo α < ε$_0$. A hierarquia de Hardy alcança a de Wainer para α = ε$_0$, tal que f$_{ε0}$ e h$_{ε0}$ possuem a mesma taxa de crescimento, em que f$_{ε0}$(n-1) ≤ h$_{ε0}$(n) ≤ f$_{ε0}$(n+1) para todo n ≥ 1. (Gallier 1991)

## Funções na hierarquia de rápido crescimento

As funções para valores finitos (α < ω) de qualquer hierarquia de rápido crescimento coincidem com os da hierarquia de Grzegorczyk :
* f$_0$(n) = n + 1
* f$_1$(n) = f$_0$$^n$(n) = n + n = 2n
* f$_2$(n) = f$_1$$^n$(n) = 2$^n$n > (2 ↑) n para n ≥ 2 (usando a Notação de Knuth)
* f$_{k+1}$(n) = f$_k$$^n$(n) > (2 ↑$^{k-1}$)$^n$ n ≥ 2 ↑$^k$ n para n ≥ 2, k < ω.
Além dos valores finitos estão as funções da hierarquia de Wainer (ω ≤ α ≤ ε$_0$):
* f$_ω$(n) = f$_n$(n) > 2 ↑$^{n-1}$ n > 2 ↑$^{n−2}$ (n + 3) − 3 = A(n, n)para n ≥ 4, onde A é a função de Ackermann (e f$_ω$ é uma versão unária).
* f$_{ω+1}$(n) = f$_ω$$^n$(n) ≥ f$_{n↑nn}$(n) para todo n > 0, em que n↑$^n$n é o n-ésimo Número de Ackermann.
* f$_{ω+1}$(64) > f$_ω$$^{64}$(6) > Número de Graham (= g$_{64}$ na sequência definida por g$_0$ = 4, g$_{k+1}$ = 3 ↑$^{gk}$ 3). Segue-se com f$_ω$(n) > 2 ↑$^{n-1}$ n > 3 ↑$^{n-2}$ 3 + 2, e portanto f$_ω$(g$_k$ + 2) > g$_{k+1}$ + 2.
* f$_{ε0}$(n) é a primeira função na hierarquia de Wainer que domina a função de Goodstein.