Hierarquia de crescimento rápido

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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α: NN (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[editar | editar código-fonte]

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α: NN, 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 fn, 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 f0 para qualquer função crescente g: NN.

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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: NN, 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.
  • 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[editar | editar código-fonte]

As funções para valores finitos (α < ω) de qualquer hierarquia de rápido crescimento coincidem com os da hierarquia de Grzegorczyk :

  • f0(n) = n + 1
  • f1(n) = f0n(n) = n + n = 2n
  • f2(n) = f1n(n) = 2nn > (2 ↑) n para n ≥ 2 (usando a Notação de Knuth)
  • fk+1(n) = fkn(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) = fn(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) ≥ fnnn(n) para todo n > 0, em que nnn é o n-ésimo Número de Ackermann.
  • fω+1(64) > fω64(6) > Número de Graham (= g64 na sequência definida por g0 = 4, gk+1 = 3 ↑gk 3). Segue-se com fω(n) > 2 ↑n - 1 n > 3 ↑n - 2 3 + 2, e portanto fω(gk + 2) > gk+1 + 2.
  • fε0(n) é a primeira função na hierarquia de Wainer que domina a função de Goodstein.

Referências[editar | editar código-fonte]

  • 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 48 (2): 399–408, doi:10.2307/2273557, ISSN 0022-4812 
  • 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.