Hierarquia de crescimento rápido - Fast-growing hierarchy

Na teoria da computabilidade , teoria da complexidade computacional e teoria da prova , uma hierarquia de crescimento rápido (também chamada de hierarquia Grzegorczyk estendida ) é uma família indexada por ordinal de funções crescentes rapidamente f _α : N → N (onde N é o conjunto de números naturais { 0, 1, ...} e α variam até algum grande ordinal contável ). Um exemplo principal é a hierarquia Wainer , ou hierarquia Löb – Wainer , que é uma extensão de todo α < ε ₀ . Essas hierarquias fornecem uma maneira natural de classificar funções computáveis ​​de acordo com a taxa de crescimento e a complexidade computacional .

Definição

Seja μ um grande ordinal contável , de modo que para cada ordinal limite α <μ é atribuída uma seqüência fundamental (uma seqüência estritamente crescente de ordinais cujo supremo é α). Uma hierarquia de rápido crescimento de funções f _α : N → N , para α <μ, é então definida da seguinte forma:

• ${\ displaystyle f_ {0} (n) = n + 1,}$
• ${\ displaystyle f _ {\ alpha +1} (n) = f _ {\ alpha} ^ {n} (n),}$
• ${\ displaystyle f _ {\ alpha} (n) = f _ {\ alpha [n]} (n)}$ se α é um limite ordinal.

Aqui f _α ⁿ ( n ) = f _α ( f _α (... ( f _α ( n )) ...)) denota o n- ^ésimo iterado de f _α aplicado a n , e α [ n ] denota o n- ^ésimo elemento da seqüência fundamental atribuído ao limite ordinal α. (Uma definição alternativa leva o número de iterações como n +1, em vez de n , na segunda linha acima.)

A parte inicial dessa hierarquia, que compreende as funções f _α com índice finito (ou seja, α <ω), é freqüentemente chamada de hierarquia de Grzegorczyk por causa de sua estreita relação com a hierarquia de Grzegorczyk ; observe, entretanto, que a primeira é aqui uma família indexada de funções f _n , enquanto a última é uma família indexada de conjuntos de funções . (Consulte Pontos de interesse abaixo.) ${\ displaystyle {\ mathcal {E}} ^ {n}}$

Generalizando a definição acima ainda mais, uma hierarquia de iteração rápida é obtida tomando f ₀ para ser qualquer função crescente g: N → N .

Para limites ordinais não maiores que ε ₀ , há uma definição natural direta das sequências fundamentais (veja a hierarquia de Wainer abaixo), mas além de ε ₀ a definição é muito mais complicada. No entanto, isso é possível muito além do ordinal Feferman-Schütte, Γ ₀ , até pelo menos o ordinal de Bachmann-Howard . Usando as funções psi de Buchholz, pode-se estender essa definição facilmente ao ordinal da compreensão iterada transfinitamente (ver Hierarquia analítica ). ${\ displaystyle \ Pi _ {1} ^ {1}}$

Uma extensão totalmente especificada além dos ordinais recursivos é considerada improvável; por exemplo, Prӧmel et al. [1991] (p. 348) observam que em tal tentativa "haveria mesmo problemas na notação ordinal".

A hierarquia Wainer

A hierarquia Wainer é a hierarquia particular de crescimento rápido de funções f _α (α ≤ ε ₀ ) obtida pela definição das sequências fundamentais como segue [Gallier 1991] [Prӧmel, et al., 1991]:

Para limites ordinais λ < ε ₀ , escritos na forma normal de Cantor ,

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

e

• se λ = ε ₀ , tome λ [0] = 0 e λ [ n + 1] = ω ^{λ [ n ]} como em [Gallier 1991]; alternativamente, tome a mesma sequência, exceto começando com λ [0] = 1 como em [Prӧmel, et al., 1991].
  Para n > 0, a versão alternativa tem um ω adicional na torre exponencial resultante, ou seja, λ [ n ] = ω ^{ω . . . ω} com n ômegas.

Alguns autores usam definições ligeiramente diferentes (por exemplo, ω ^{α + 1} [ n ] = ω ^α ( n + 1 ), em vez de ω ^α n ), e alguns definem esta hierarquia apenas para α <ε ₀ (excluindo assim f _{ε 0} de a hierarquia).

Para continuar além de ε ₀ , consulte as Sequências fundamentais para a hierarquia de Veblen .

Pontos de interesse

A seguir estão alguns pontos de interesse relevantes sobre hierarquias de rápido crescimento:

• Todo f _α é uma função total . Se as sequências fundamentais são computáveis ​​(por exemplo, como na hierarquia de Wainer), então todo f _α é uma função computável total .
• Na hierarquia de Wainer, f _α é dominado por f _β se α <β. (Para quaisquer duas funções f , g : N → N , f é dito para dominar g , se f ( n )> g ( n ) para todos suficientemente grande n .) A mesma propriedade mantém em qualquer hierarquia de crescimento rápido com sequências fundamentais satisfazendo a chamada propriedade de Bachmann . (Esta propriedade é válida para a maioria das ordenações de poços naturais.)
• Na hierarquia de Grzegorczyk, toda função recursiva primitiva é dominada por algum f _α com α <ω. Portanto, na hierarquia de Wainer, toda função recursiva primitiva é dominada por f _ω , que é uma variante da função de Ackermann .
• Para n ≥ 3, o conjunto na hierarquia de Grzegorczyk é composto apenas por aquelas funções multi-argumento totais que, para argumentos suficientemente grandes, são computáveis ​​dentro do tempo limitado por alguma iteração fixa f _{n -1} ^k avaliada no argumento máximo.${\ displaystyle {\ mathcal {E}} ^ {n}}$
• Na hierarquia de Wainer, todo f _α com α < ε ₀ é computável e comprovadamente total na aritmética de Peano .
• Cada função computável que é comprovadamente total na aritmética de Peano é dominada por algum f _α com α < ε ₀ na hierarquia de Wainer. Portanto, f _{ε 0} na hierarquia de Wainer não é comprovadamente total na aritmética de Peano.
• A função de Goodstein tem aproximadamente a mesma taxa de crescimento ( ou seja, cada um é dominado por algum iterado fixo do outro) que f _{ε 0} na hierarquia de Wainer, dominando todos os f _α para os quais α < ε ₀ e, portanto, não é comprovadamente total em Peano Aritmética.
• Na hierarquia de Wainer, se α <β < ε ₀ , então f _β domina todas as funções computáveis ​​dentro do tempo e espaço limitada por alguma iteração fixa f _α ^k .
• A função TREE de Friedman domina f _{Γ 0} em uma hierarquia de rápido crescimento descrita por Gallier (1991).
• A hierarquia de Wainer das funções f _α e a hierarquia de Hardy das funções h _α são relacionadas por f _α = h _{ω ^α} para todo α <ε ₀ . A hierarquia de Hardy "alcança" a hierarquia de Wainer em α = ε ₀ , de modo que f _{ε 0} e h _{ε 0} têm a mesma taxa de crescimento, no sentido de que f _{ε 0} ( n -1) ≤ h _{ε 0} ( n ) ≤ f _{ε 0} ( n +1) para todo n ≥ 1. (Gallier 1991)
• Girard (1981) e Cichon & Wainer (1983) mostraram que a hierarquia de crescimento lento das funções g _α atinge a mesma taxa de crescimento que a função f _{ε 0} na hierarquia de Wainer quando α é o ordinal de Bachmann-Howard . Girard (1981) mostrou ainda que a hierarquia de crescimento lento g _α atinge a mesma taxa de crescimento que f _α (em uma hierarquia de crescimento rápido particular) quando α é o ordinal da teoria ID _<ω de iterações finitas arbitrárias de uma definição indutiva . (Wainer 1989)

Funções em hierarquias de rápido crescimento

As funções em níveis finitos (α <ω) de qualquer hierarquia de crescimento rápido coincidem com as da hierarquia de Grzegorczyk: (usando hiperoperação )

• f ₀ ( n ) = n + 1 = 2 [1] n - 1
• f ₁ ( n ) = f ₀ ⁿ ( n ) = n + n = 2 n = 2 [2] n
• f ₂ ( n ) = f ₁ ⁿ ( n ) = 2 ⁿ · n > 2 ⁿ = 2 [3] n para n ≥ 2
• f _{k +1} ( n ) = f _k ⁿ ( n )> (2 [ k + 1]) ⁿ n ≥ 2 [ k + 2] n para n ≥ 2, k <ω.

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

• f _ω ( n ) = f _n ( n )> 2 [ n + 1] n > 2 [ n ] ( n + 3) - 3 = A ( n , n ) para n ≥ 4, onde A é a função de Ackermann ( do qual f _ω é uma versão unária).
• f _{ω + 1} ( n ) = f _ω ⁿ ( n ) ≥ f _{N [ n + 2] n} ( n ) para todos os n > 0, em que n [ n + 2] n é o n ^th número Ackermann .
• f _{ω + 1} (64)> f _ω ⁶⁴ (5)> Número de Graham (= g ₆₄ na sequência definida por g ₀ = 4, g _{k +1} = 3 [ g _k + 2] 3). Isso segue observando f _ω ( n )> 2 [ n + 1] n > 3 [ n ] 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, SS (1987). "Provably Computable Functions and the Fast Growing Hierarchy". Logic and Combinatorics , editado por S. Simpson, Contemporary Mathematics, Vol. 65, AMS, 179-198.
• Cichon, EA; Wainer, SS (1983), "The slow-growth and the Grzegorczyk hierarchies", The Journal of Symbolic Logic , 48 (2): 399-408, doi : 10.2307 / 2273557 , ISSN  0022-4812 , MR  0704094
• Gallier, Jean H. (1991), "O que há de tão especial sobre o teorema de Kruskal e o ordinal Γ ₀ ? Um levantamento de alguns resultados na teoria da prova", Ann. Pure Appl. Logic , 53 (3): 199-260, doi : 10.1016 / 0168-0072 (91) 90022-E , MR  1129778PDF: [1] . (Em particular a Seção 12, pp. 59-64, "Um Vislumbre das Hierarquias das Funções de Crescimento Rápido e Lento".)
• Girard, Jean-Yves (1981), "Π ¹ ₂ -logic. I. Dilators", Annals of Mathematical Logic , 21 (2): 75–219, doi : 10.1016 / 0003-4843 (81) 90016-4 , ISSN  0003-4843 , MR  0656793
• Lob, MH; Wainer, SS (1970), "Hierarchies of number Theoretic functions", Arch. Matemática. Logik , 13 anos. Correção, Arch. Matemática. Logik , 14, 1971. Parte I doi : 10.1007 / BF01967649 , Parte 2 doi : 10.1007 / BF01973616 , Correções doi : 10.1007 / BF01991855 .
• Prömel, HJ; Thumser, W .; Voigt, B. "Funções de crescimento rápido baseadas em teoremas de Ramsey", Discrete Mathematics , v.95 n.1-3, p. 341-358, December 1991 doi : 10.1016 / 0012-365X (91) 90346-4 .
• Wainer, SS (1989). "Crescimento lento versus crescimento rápido". Journal of Symbolic Logic . 54 (2): 608–614. JSTOR  2274873 .