Hierarquia de crescimento lento

Origem: Wikipédia, a enciclopédia livre.

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α: NN (onde N é um conjunto de Números Naturais, {0, 1, ...}). Em contraste com Hierarquia de crescimento rápido.

Definição[editar | editar código-fonte]

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α: NN para α < μ, é definida abaixo:

  • 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 α < ε0.

Relacionamento com Hierarquia de crescimento rápido[editar | editar código-fonte]

Uma hierarquia de crescimento lento cresce muito mais lentamente que uma hierarquia de crescimento rápido. Até mesmogε0 só é equivalente à f3 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 ε0 (Weiermann 1997).

Extensões do resultado provaram em Wainer 1989 para grandes ordinais consideráveis, mostraram que existem poucos ordinais abaixo do iterado transfinitamente -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[editar | editar código-fonte]

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

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