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 α < ε₀. 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) = 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₀ para qualquer função crescente g: N → N.

Para ordinais limite não maiores que ε₀ (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 ε₀, a definição é muito mais complicada. Porém, isso é possível para além do ordinal de Feferman–Schütte Γ₀, 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_α (α ≤ ε₀) obtido através da definição das sequências fundamentais da seguinte forma [Gallier 1991][Prӧmel, et al, 1991.]: Para ordinais limite λ < ε₀, escrita na Forma Normal de Cantor :

• se λ = ω^α₁ + ... + ω^α_k−1 + ω^α_k for α₁ ≥ ... ≥ α_k−1 ≥ α_k, então λ[n] = ω^α₁ + ... + ω^α_k−1 + ω^α_k[n],
• se λ = ω^α+1, então λ[n] = ω^αn,
• se λ = ω^α para o ordinal limite α, então λ[n] = ω^α[n],

e

• se λ = ε₀, 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 α < ε₀ (excluindo f_ε0 da hierarquia).

Para ir além do ε₀, 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 α < ε₀ é 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 α < ε₀ 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 α < ₀, e, portanto, não é comprovadamente total na Aritmética Peano.
• Na hierarquia de Wainer, se α < β < ε₀, 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 α < ε₀. A hierarquia de Hardy alcança a de Wainer para α = ε₀, 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₀(n) = n + 1
• f₁(n) = f₀ⁿ(n) = n + n = 2n
• f₂(n) = f₁ⁿ(n) = 2ⁿn > (2 ↑) n para n ≥ 2 (usando a Notação de Knuth)
• f_k+1(n) = f_kⁿ(n) > (2 ↑^k-1)ⁿ n ≥ 2 ↑^k n para n ≥ 2, k < ω.

Além dos valores finitos estão as funções da hierarquia de Wainer (ω ≤ α ≤ ε₀):

• 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) ≥ f_n↑ⁿn(n) para todo n > 0, em que n↑ⁿn é o n-ésimo Número de Ackermann.
• f_ω+1(64) > f_ω⁶⁴(6) > Número de Graham (= g₆₄ na sequência definida por g₀ = 4, g_k+1 = 3 ↑^g_k 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.

Referências

• Buchholz, W.; Wainer, S.S (1987). "Provably Computable Functions and the Fast Growing Hierarchy". Logic and Combinatorics, edited by S. Simpson, Contemporary Mathematics, Vol. 65, AMS, 179-198.
• Cichon, E. A.; Wainer, S. S. (1983), «The slow-growing and the Grzegorczyk hierarchies», The Journal of Symbolic Logic, ISSN 0022-4812, 48 (2): 399–408, MR 704094, doi:10.2307/2273557 
• Gallier, Jean H. (1991), «What's so special about Kruskal's theorem and the ordinal Γ₀? A survey of some results in proof theory», Ann. Pure Appl. Logic, 53 (3): 199–260, MR 1129778, doi:10.1016/0168-0072(91)90022-E ^{[ligação inativa]} PDF's: part 1 2 3. (In particular part 3, Section 12, pp. 59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions".)
• Girard, Jean-Yves (1981), «Π¹₂-logic. I. Dilators», Annals of Mathematical Logic, ISSN 0003-4843, 21 (2): 75–219, MR 656793, doi:10.1016/0003-4843(81)90016-4 
• Löb, M.H.; Wainer, S.S. (1970), "Hierarchies of number theoretic functions", Arch. Math. Logik, 13. Correction, Arch. Math. Logik, 14, 1971. Part I doi:10.1007/BF01967649, Part 2 doi:10.1007/BF01973616, Corrections doi:10.1007/BF01991855.
• Prömel, H. J.; Thumser, W.; Voigt, B. "Fast growing functions based on Ramsey theorems", Discrete Mathematics, v.95 n.1-3, p. 341-358, Dec. 1991 doi:10.1016/0012-365X(91)90346-4.
• Wainer, S.S (1989), "Slow Growing Versus Fast Growing". Journal of Symbolic Logic 54(2): 608-614.