Mostrar código-fonte de Hierarquia de crescimento lento

{{sem notas||ci|data=julho de 2012}}
{{Reciclagem||ci|data=julho de 2012}}
Nas áreas de [[Teoria da Computabilidade]], [[Complexidade computacional]] e[[Teoria da Prova]], uma '''Hierarquia de Crescimento Lento''' é uma família  ordinal indexada de funções de crescimento lento.''g''<sub>α</sub>: '''N''' → '''N''' (onde '''N''' é um conjunto de [[Número natural|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''<sub>α</sub>: '''N''' → '''N''' para α < μ, é definida abaixo:

* <math> g_0(n) = 0,\, </math>
* <math> g_{\alpha+1}(n) = g_\alpha(n) + 1,\, </math>
* <math> g_\alpha(n) = g_{\alpha[n]}(n) \,\!</math> 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 α < ε<sub>0</sub>.

== Relacionamento com Hierarquia de crescimento rápido ==
Uma hierarquia de crescimento lento cresce muito mais lentamente que uma hierarquia de crescimento rápido. Até mesmo''g''<sub>[[ε0|ε<sub>0</sub>]]</sub> só é equivalente à ''f''<sub>3</sub> e ''g''<sub>α</sub> só alcança o crescimento de ''f''<sub>ε<sub>0</sub></sub> (a primeira função da aritmética descrita nos [[Axiomas de Peano]] não pode provar [[Ordem_total#Rela.C3.A7.C3.A3o_de_ordem_total|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''<sub>α</sub>(''n'') < ''f''<sub>α</sub>(''n'') < ''g''<sub>α</sub>(''n'' + 1)
onde ''f''<sub>α</sub> são funções na hierarquia de crescimento rápido. Indo mais longe, ele mostrou que o primeiro α, isso vale para da teoria ''ID''<sub><ω</sub> 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 ε<sub>0</sub> (Weiermann 1997).

Extensões do resultado provaram em Wainer 1989 para grandes ordinais consideráveis, mostraram que existem poucos ordinais abaixo do iterado transfinitamente <math>\Pi^1_1</math>-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 ==
*{{citar periódico|último1 =Girard |primeiro1 =Jean-Yves |autorlink1 =Jean-Yves Girard |título=Π<sup>1</sup><sub>2</sub>-logic. I. Dilators | doi=10.1016/0003-4843(81)90016-4 | mr=656793 |ano=1981 |periódico=Annals of Mathematical Logic | issn=0003-4843 | volume=21 |número=2 |páginas=75–219 }}
*{{citar periódico|último1 =Cichon |primeiro1 =E. A. |último2 =Wainer |primeiro2 =S. S. |título=The slow-growing and the Grzegorczyk hierarchies | doi=10.2307/2273557 | mr=704094 |ano=1983 |periódico=The Journal of Symbolic Logic | issn=0022-4812 | volume=48 |número=2 |páginas=399–408 }}
*{{citar periódico|jstor=2274873 |páginas=608–614 |último1 =Wainer |primeiro1 =S. S. |título=Slow Growing Versus Fast Growing |volume=54 |número=2 |periódico=The Journal of Symbolic Logic |ano=1989 |doi=10.2307/2274873}}
*{{citar periódico|mr=1129778|último=Gallier|primeiro=Jean H.|título=What's so special about Kruskal's theorem and the ordinal Γ<sub>0</sub>? A survey of some results in proof theory|periódico=Ann. Pure Appl. Logic|volume=53|ano=1991|número=3|páginas=199–260|url=http://stinet.dtic.mil/oai/oai?verb=getRecord&metadataPrefix=html&identifier=ADA290387|doi=10.1016/0168-0072(91)90022-E}}{{Ligação inativa|1=data=abril de 2019 }} PDF's: [ftp://ftp.cis.upenn.edu/pub/papers/gallier/kruskal1.pdf part 1] [ftp://ftp.cis.upenn.edu/pub/papers/gallier/kruskal2.pdf 2] [ftp://ftp.cis.upenn.edu/pub/papers/gallier/kruskal3.pdf 3]. (In particular part 3, Section 12, pp.&nbsp;59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions".)
* {{citar livro|último =Cichon|título=Proof Theory|ano=1992|publicado=Cambridge University Press|páginas=173–193|editor=P. Aczel, H. Simmons, S. Wainer|capítulo=Termination Proofs and Complexity Characterisations}}
* {{citar periódico|último =Weiermann |primeiro =A. |ano=1995 |título= |periódico=Archives of Mathematical Logic |volume= 34 |páginas=313–330 |doi= }}
* {{citar periódico|doi=10.1016/S0168-0072(97)00033-X |título=Sometimes slow growing is fast growing |ano=1997 |último1 =Weiermann |primeiro1 =A |periódico=Annals of Pure and Applied Logic |volume=90 |páginas=91}}
* Weiermann, A. (1999), [http://books.google.com/books?id=2IHm3RT2bBoC&lpg=PP1&pg=PA403#v=onepage&q=&f=false "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.

[[Categoria:Teoria da computabilidade]]