Hierarquia de rápido crescimento

Na computabilidade e teoria da prova , uma hierarquia de crescimento rápido (às vezes chamada de hierarquia de Grzegorczyk estendida ) é uma família , indexada por ordinais , de funções crescentes rapidamente f α : N → N (onde N é l 'conjunto de números naturais {0, 1 ,…}, E α é um ordinal menor que um certo ordinal contável que geralmente é muito grande ). Um exemplo fundamental é a hierarquia Wainer , estendendo-se a todos α < ε₀ (in) . Essas hierarquias fornecem uma maneira natural de classificar funções computáveis de acordo com sua taxa de crescimento e complexidade algorítmica ; eles também tornam possível expressar números muito grandes, como aqueles produzidos pelas sequências de Goodstein , quando mesmo a notação das flechas encadeadas de Conway não é mais suficiente.

Definição

Seja μ um ordinal grande contável de modo que, para cada ordinal limite α menor que μ, seja dada uma seqüência fundamental , ou seja, uma seqüência estritamente crescente de ordinais com limite α. Em seguida, definimos uma hierarquia de funções f α : N → N , para α <μ, 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 ( n ) = f α ( f α (... ( f α ( n )) ...)) indica o n th iterado de f α aplicado a n , e α [ n ] o n th elemento da seqüência fundamental escolhido para o limite ordinal α.

A parte inicial desta hierarquia, formada por funções f α de índice finito (ou seja, com α <ω), é frequentemente chamada de hierarquia de Grzegorczyk por causa de sua estreita relação com a hierarquia de conjuntos de funções definidas por ela, como veremos mais tarde .

Generalizando ainda mais a definição anterior, uma hierarquia de iterações é obtida tomando para f 0 qualquer função estritamente crescente g : N → N tal que g (0)> 0.

Para ordinais limite menores que ε₀ (en) , há uma definição natural das sequências fundamentais, como veremos a seguir na descrição detalhada da hierarquia Wainer, mas para ordinais maiores, a definição torna-se muito mais complicada, pedindo por exemplo o uso das sequências fundamentais da hierarquia de Veblen . No entanto, permanece possível mesmo além do ordinal Feferman-Schütte , Γ 0 , pelo menos até o ordinal Bachmann Howard (em) . Usando as funções psi de Buchholz (en) , podemos estender ainda mais essa definição para o ordinal de compreensão iterada transfinidamente (consulte a hierarquia analítica para obter mais detalhes). $\ Pi _ {1} ^ {1}$

Parece improvável que possamos construir uma extensão explícita além dos ordinais recursivos ; assim, Prömel observa que, em tal tentativa, "haveria mesmo dificuldades na notação dos ordinais".

Hierarquia de Wainer

A hierarquia Wainer é o caso particular da hierarquia de funções f α (α ≤ ε 0 ) obtida pela definição das sequências fundamentais da seguinte forma:

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

se λ = ω α 1 + ... + ω α k - 1 + ω α k com α 1 ≥ ... ≥ α k - 1 ≥ α k , então λ [ n ] = ω α 1 + ... + ω α k - 1 + ω α k [ n ],
se λ = ω α + 1 , então λ [ n ] = ω α n ,
se λ = ω α para um limite ordinal α, então λ [ n ] = ω α [ n ] ,

se λ = ε 0 , tome λ [0] = 0 e λ [ n + 1] = ω λ [ n ] .

Alguns autores usam definições ligeiramente diferentes (por exemplo, ω α + 1 [ n ] = ω α ( n + 1 ), em vez de ω α ( n ), ou definem apenas para α <ε 0 (excluindo f ε 0 do hierarquia).

Propriedades das hierarquias

Cada f α é uma aplicação . Se as sequências fundamentais são computáveis (como no caso da hierarquia Wainer), cada f α é uma função computável .
Na hierarquia de Wainer, f α é dominado por f β se α <β (para duas funções f e g : N → N , dizemos que f domina g se f ( n )> g ( n ) para todo n suficientemente grande) . A mesma propriedade é de fato verdadeira para a maioria das hierarquias mencionadas acima (quando elas correspondem a sequências fundamentais que satisfazem uma condição adicional bastante natural, a propriedade de Bachmann ).
Na hierarquia de Grzegorczyk, cada função recursiva primitiva é dominada por um certo f α com α <ω. Portanto, na hierarquia de Wainer, todas as funções recursivas primitivas são dominadas por f ω (que é uma variante da função de Ackermann ).
Para n ≥ 3, o conjunto na hierarquia (conjunto) de Grzegorczyk é composto de mapeamentos computáveis para várias variáveis que, para valores grandes o suficiente de seus argumentos, são computáveis no tempo limitado por um f n -1 k iterado (com k fixo) avaliado no maior argumento. ${\ mathcal {E}} ^ {n}$
Na hierarquia de Wainer, cada f α com α <ε 0 é computável por uma máquina de Turing cuja parada (para qualquer valor de entrada) pode ser demonstrada na aritmética de Peano .
Por outro lado, qualquer função computável por uma máquina de Turing cuja parada pode ser demonstrada na aritmética de Peano é dominada por um f α da hierarquia de Wainer, com α <ε 0 . Assim, não podemos provar que a função f ε 0 é uma aplicação que usa apenas os axiomas de Peano.
A função Goodstein cresce aproximadamente como f ε 0 , e domina todo f α para α <ε 0 , portanto o teorema de Goodstein não pode ser demonstrado na aritmética de Peano .
Na hierarquia de Wainer, se α <β <ε 0 , então f β domina qualquer função computável no tempo e no espaço limitada por uma função iterada f α k .

As funções das hierarquias de rápido crescimento

Além do valor f α ( 1 ) = 2 para todos os α, e desde os primeiros níveis da hierarquia, é geralmente impossível dar um valor exato dessas funções usando as notações exponenciais usuais, nem mesmo usando as várias notações inventado para descrever números inteiros muito grandes, eles crescem tão rápido. As reduções dadas abaixo, portanto, fornecem apenas uma ordem de magnitude muito grosseira, além de serem ridiculamente fracas pela função f ω 2 ( n ).

As funções dos níveis finitos de qualquer hierarquia de crescimento rápido coincidem com as da hierarquia Grzegorczyk:

f 0 ( n ) = n + 1
f 1 ( n ) = f 0 n ( n ) = n + n = 2 n
f 2 ( n ) = f 1 n ( n ) = 2 n n
f 3 ( n ) = f 2 n ( n ) ≥ 2 ↑↑ n para n ≥ 2 (usando a notação de seta de Knuth )
f k +1 ( n ) = f k n ( n )> (2 ↑ k -1 ) n n ≥ 2 ↑ k n para n ≥ 2, k <ω (onde ↑ k = ↑↑↑ ... ↑↑ , com k setas).

Em seguida, encontramos as funções f α da hierarquia Wainer (ω ≤ α ≤ ε 0 ):

f ω ( n ) = f n ( n )> 2 ↑ n - 1 n > 2 ↑ n - 2 ( n + 3) - 3 = A ( n , n ) para n ≥ 2, onde A é a função de Ackermann (da qual f ω é uma versão unária).
f ω + 1 ( n ) = f ω n ( n )> (2 → n → n -1 → 2) (usando a notação de seta em cadeia de Conway ), porque se g k ( n ) = X → n → k , então X → n → k +1 = g k n (1), e em particular
f ω + 1 (64)> f ω 64 (6)> G, o número de Graham (G = g 64 na sequência definida por g 0 = 4, g k +1 = 3 ↑ g k 3). Isso decorre do fato de que f ω ( n )> 2 ↑ n - 1 n > 3 ↑ n - 2 3 + 2 e, portanto, f ω ( g k + 2)> g k +1 + 2.
f ω + k ( n )> (2 → n → n -1 → k +1)> ( n → n → k )
f ω2 ( n ) = f ω + n ( n )> ( n → n → n )
f ω2 + k ( n )> ( n → n → n → k )
f ω3 ( n )> ( n → n → n → n )
f ω k ( n )> ( n → n → ... → n → n ) (string formada por k setas →)
f ω 2 ( n ) = f ω n ( n )> ( n → n → ... → n → n ) (com n setas →)
f ε 0 ( n ) é a primeira função da hierarquia de Wainer que domina a função de Goodstein G (n) (que pode, além disso, ser expressa exatamente usando as funções f α ; assim, temos G (4) = f ω (3) - 2, G (8) = f ω + 1 (3) - 2 e G (19) = ). $\ scriptstyle f _ {{\ omega ^ {\ omega}}} (f_ {1} (f_ {0} (3))) - 2 = f _ {{\ omega ^ {\ omega}}} (8) - 2 = f _ {{\ omega ^ {8}}} (8) -2 = f _ {{\ omega ^ {7} .8}} (8) -2 = f _ {{\ omega ^ {7} .7 + 8}} (8) -2 = \ pontos$

Notas e referências

(fr) Este artigo foi retirado parcial ou totalmente do artigo da Wikipedia em inglês intitulado " Fast-growth hierarchy " ( veja a lista de autores ) .

Prömel, Thumser e Voigt 1991 , p. 348.
Gallier 1991 ; Prömel, Thumser e Voigt 1991 .
Caicedo 2007 , Teorema 1.11.

Apêndices

Bibliografia

(pt) W. Buchholz e SS Wainer, "Provably Computable Functions and the Fast Growing Hierarchy". Logic and Combinatorics , editado por S. Simpson, Contemporary Mathematics, Vol. 65, AMS (1987), 179-198.
(en) Andrés Eduardo Caicedo , “ A função de Goodstein ” , Revista Colombiana de Matemáticas , vol. 41, n o 22007, p. 381-391 ( ler online ).
(pt) EA Cichon e SS Wainer , “ The slow-growth and the Grzegorczyk hierarchies ” , The Journal of Symbolic Logic , vol. 48, n o 21983, p. 399-408 ( ISSN 0022-4812 , DOI 10.2307 / 2273557 ), Link Resenhas de matemática
(pt) Jean H. Gallier , “ O que há de tão especial sobre o teorema de Kruskal e o ordinal Γ 0 ? Um levantamento de alguns resultados na teoria da prova ” , Ann. Pure Appl. Logic , vol. 53, n o 3,1991, p. 199-260 ( DOI 10.1016 / 0168-0072 (91) 90022-E , ler online ), Link de revisões de matemática , PDFs: parte 1 2 3 (em particular parte 3, seção 12, pp. 59-64, "Um vislumbre das hierarquias das funções de crescimento rápido e lento").
Jean-Yves Girard , “ Π 1 2 -Logic. I. Dilators ”, Annals of Mathematical Logic , vol. 21, n o 2Mil novecentos e oitenta e um, p. 75-219 ( ISSN 0003-4843 , DOI 10.1016 / 0003-4843 (81) 90016-4 ), Link Resenhas de matemática
(pt) MH Löb e SS Wainer, "Hierarchies of number Theoretic functions", Arch. Matemática. Logik 13 (1970). 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 .
(pt) HJ Prömel , W. Thumser e B. Voigt , “ Funções de crescimento rápido baseadas em teoremas de Ramsey ” , Discrete Mathematics , vol. 95, n osso 1-3,Dezembro de 1991, p. 341-358 ( DOI 10.1016 / 0012-365X (91) 90346-4 ).
(pt) SS Wainer, " Slow Growing Versus Fast Growing ". Journal of Symbolic Logic 54 (2) (1999), 608-614.