Hierarquia de crescimento lento

Nas áreas de Teoria da Computabilidade, Complexidade computacional eTeoria da Prova, uma Hierarquia de Crescimento Lento é uma família ordinal indexada de funções de crescimento lento.g_α: N → N (onde N é um conjunto de Números Naturais, {0, 1, ...}). Em contraste com Hierarquia de crescimento rápido.

Definição

Sendo μ um alguns ordinais contáveis “enormes” tal que uma sequência fundamental é atribuída a todo ordinal limite é menor que μ. A hierarquia de crescimento lento das funções g_α: N → N para α < μ, é definida abaixo:

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

Onde α[n] denota o enésimo elemento da sequência fundamental atribuída ao ordinal limite α.

O artigo sobre Hierarquia de crescimento rápido descreve uma seleção comum para a sequência fundamental atribuida a α < ε₀.

Relacionamento com Hierarquia de crescimento rápido

Uma hierarquia de crescimento lento cresce muito mais lentamente que uma hierarquia de crescimento rápido. Até mesmog_ε0 só é equivalente à f₃ e g_α só alcança o crescimento de f_ε0 (a primeira função da aritmética descrita nos Axiomas de Peano não pode provar total na hierarquia) quando α é um o Ordinal de Bachmann-Howard. (Girard 1981) e(Cichon eWainer 1983)

No entanto, Girard (1981) provou que uma hierarquia de crescimento lento eventualmente alcança uma de crescimento rápido. Especificamente, que existe um ordinal α e inteiros a, b tais que

g_α(n) < f_α(n) < g_α(n + 1)

onde f_α são funções na hierarquia de crescimento rápido. Indo mais longe, ele mostrou que o primeiro α, isso vale para da teoria ID_<ω de uma definição indutiva de iterações finitas arbitrárias. (Wainer 1989). Entretanto para Cichon (1992) a atribuição de sequências fundamentais ocorrem primeiramente no nível ε₀ (Weiermann 1997).

Extensões do resultado provaram em Wainer 1989 para grandes ordinais consideráveis, mostraram que existem poucos ordinais abaixo do iterado transfinitamente ${\displaystyle \Pi _{1}^{1}}$-compreensão onde hierarquias de crescimento tanto lento quanto rápido se igualam (Weiermann 1995).

Para os novatos é importante mencionar que hierarquias de crescimento lento dependem profundamente da escolha da sequência fundamental (Weiermann 1997 e Weiermann 1999).

Relação com reescrita de termos

Cichon desenvolveu uma conexão interessante entre hierarquias de crescimento lento e derivação de comprimento para reescrita de termos (Cichon 1990).

Referências

• Girard, Jean-Yves (1981). «Π¹₂-logic. I. Dilators». Annals of Mathematical Logic. 21 (2): 75–219. ISSN 0003-4843. MR 656793. doi:10.1016/0003-4843(81)90016-4 
• Cichon, E. A.; Wainer, S. S. (1983). «The slow-growing and the Grzegorczyk hierarchies». The Journal of Symbolic Logic. 48 (2): 399–408. ISSN 0022-4812. MR 704094. doi:10.2307/2273557 
• Wainer, S. S. (1989). «Slow Growing Versus Fast Growing». The Journal of Symbolic Logic. 54 (2): 608–614. JSTOR 2274873. doi:10.2307/2274873 
• 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".)
• Cichon (1992). «Termination Proofs and Complexity Characterisations». In: P. Aczel, H. Simmons, S. Wainer. Proof Theory. [S.l.]: Cambridge University Press. pp. 173–193  !CS1 manut: Nomes múltiplos: lista de editores (link)
• Weiermann, A. (1995). Archives of Mathematical Logic. 34: 313–330 
• Weiermann, A (1997). «Sometimes slow growing is fast growing». Annals of Pure and Applied Logic. 90. 91 páginas. doi:10.1016/S0168-0072(97)00033-X 
• Weiermann, A. (1999), "What makes a (pointwise) subrecursive hierarchy slow growing?" Cooper, S. Barry (ed.) et al., Sets and proofs. Invited papers from the Logic colloquium '97, European meeting of the Association for Symbolic Logic, Leeds, UK, July 6–13, 1997. Cambridge: Cambridge University Press. Lond. Math. Soc. Lect. Note Ser. 258; 403-423.