Hierarquia de Grzegorczyk

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

A hierarquia de Grzegorczyk (pronúncia: [ɡʐɛˈɡɔrt​͡ʂɨk]), denominação em referência ao lógico polaco Andrzej Grzegorczyk, é uma hierarquia de funções usadas em teoria da computação (Wagner and Wechsung 1986:43). Toda função na hierarquia de Grzegorczyk é uma função recursiva primitiva, e toda função recursiva primitiva aparece na hierarquia em algum nível. A hierarquia lida com taxas de funções crescentes. Intuitivamente, funções em níveis baixos da hierarquia crescem mais devagar que funções em níveis mais altos.

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

Primeiro introduzimos um conjunto infinito de funções, denotadas Ei para algum número natural i. Definimos e , i.e, E0 é a função adicional, e E1 é uma função unária que eleva seus argumentos ao quadrado e soma dois. Depois, para cada n maior que 1, definimos .

Dessas funções definimos a hierarquia de Grzegorczy. , o n-ésimo conjunto de hierarquias, contém as seguintes funções:

  1. Ek para k < n
  2. A função zero (Z(x) = 0);
  3. A função sucessor (S(x) = x + 1);
  4. A função de projeção ();
  5. A composição de funções (generalizada) no conjunto (se h, g1, g2, ... e gm estão em , então também estão)[Perceba 1]; e
  6. O resultado da recursão limitada (primitiva) aplicada a funções no conjunto, (se g, h e j estão em e para todo t e , e mais e , então f está em também)[Perceba 1]

Em outras palavras, é o fechamento do conjunto com respeito a composição de funções e recursão limitada (como definido acima).

Propriedades[editar | editar código-fonte]

Esses conjuntos claramente são da hierarquia

porque eles são fechados sob a 's e .

Eles são subconjuntos próprios (Rose 1984; Gakwaya 1997). Em outras palavras

porque a hiperoperação está em mas não em .

  • inclui funções como x+1, x+2, ...
  • provê todas as funções adicionais, tais como x+y, 4x, ...
  • provê todas as funções de multiplicação, tais como xy, x4
  • provê todas as funções exponenciais, tais como xy, 222x, e é exatamente função recursiva elementar.
  • provê todas as funções de tetração, e assim por diante.

Relação com as funções recursivas primitivas[editar | editar código-fonte]

A definição de é a mesma de função recursiva primitiva, RP, exceto que recursão é limitada ( para algum j em ) e as funções são explicitamente incluidas em . Assim, a hierarquia de Grzegorczyk pode ser vista como um caminho para o limite do poder de recursões primitivas de diferentes níveis.

Está claro deste fato que todas as funções em qualquer nível da hierarquia de Grzegorczyk são funções recursivas primitivas (i.e. ) e assim:

Também pode ser demonstrado que todas as funções recursivas primitivas estão em algum nível da hierarquia (Rose 1984; Gakwaya 1997), assim

e conjuntos [[partição de conjunto|particiona]] o conjunto de funções recursivas primitivas, PR.


Extensões[editar | editar código-fonte]

Ver artigo principal: Hierarquia de crescimento rápido

A hierarquia de Grzegorczyk pode ser estendida para ordinal transfinito. Tal extensão define uma hierarquia de crescimento rápido. Para fazer isso, as funções geradoras tem que ser recursivamente definida por ordinais limitados (observe que eles já eram recursivamente definidos para ordinais sucessores pela relação ). Se existe uma forma padrão de definir a sequencia fundamental , cujo ordinal limitado é , então a função geradora pode ser definida como . Contudo, esta definição depende de um padrão de se definir a sequencia fundamental. Rose (1984) sugere uma forma padrão para todo ordinal α < ε0.

A extensão original foi devido a Martin Löb e Stan S. Wainer (1970) e as vezes é chamada de Löb–Wainer hierarchy.

Notas[editar | editar código-fonte]

  1. a b Perceba: Aqui representa uma tupla de entrada para f. A notação significa que faceita algumnúmero de argumento arbitrário e se , então . Na notação , o primeiro argumento, t, é especificamente explicitado e o resto é uma tupla arbitrária . assim, se , então . Esta notação permite a composição e recursão limitada serem definidas por funções, f, com qualquer número de argumentos.

Bibliografia[editar | editar código-fonte]