Hierarquia de Grzegorczyk

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

Primeiro introduzimos um conjunto infinito de funções, denotadas E_i para algum número natural i. Definimos $E_{0}(x,y)=x+y$ e $E_{1}(x)=x^{2}+2$, i.e, E₀ é a função adicional, e E₁ é uma função unária que eleva seus argumentos ao quadrado e soma dois. Depois, para cada n maior que 1, definimos $E_{n}(x)=E_{n-1}^{x}(2)$.

Dessas funções definimos a hierarquia de Grzegorczy. ${\mathcal {E}}^{n}$, o n-ésimo conjunto de hierarquias, contém as seguintes funções:

1. E_k 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 ($p_{i}^{m}(t_{1},t_{2},\dots ,t_{m})=t_{i}$);
5. A composição de funções (generalizada) no conjunto (se h, g₁, g₂, ... e g_m estão em ${\mathcal {E}}^{n}$, então $f({\bar {u}})=h(g_{1}({\bar {u}}),g_{2}({\bar {u}}),\dots ,g_{m}({\bar {u}}))$ também estão); e
6. O resultado da recursão limitada (primitiva) aplicada a funções no conjunto, (se g, h e j estão em ${\mathcal {E}}^{n}$ e $f(t,{\bar {u}})\leq j(t,{\bar {u}})$ para todo t e ${\bar {u}}$, e mais $f(0,{\bar {u}})=g({\bar {u}})$ e $f(t+1,{\bar {u}})=h(t,{\bar {u}},f(t,{\bar {u}}))$, então f está em ${\mathcal {E}}^{n}$ também)

Em outras palavras, ${\mathcal {E}}^{n}$ é o fechamento do conjunto $B_{n}=\{Z,S,(p_{i}^{m})_{i\leq m},E_{k}:k<n\}$ com respeito a composição de funções e recursão limitada (como definido acima).

Propriedades

Esses conjuntos claramente são da hierarquia

${\mathcal {E}}^{0}\subseteq {\mathcal {E}}^{1}\subseteq {\mathcal {E}}^{2}\subseteq \cdots$

porque eles são fechados sob a $B_{n}$'s e $B_{0}\subseteq B_{1}\subseteq B_{2}\subseteq \cdots$.

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

${\mathcal {E}}^{0}\subsetneq {\mathcal {E}}^{1}\subsetneq {\mathcal {E}}^{2}\subsetneq \cdots$

porque a hiperoperação $H_{n}$ está em ${\mathcal {E}}^{n}$ mas não em ${\mathcal {E}}^{n-1}$.

• ${\mathcal {E}}^{0}$ inclui funções como x+1, x+2, ...
• ${\mathcal {E}}^{1}$ provê todas as funções adicionais, tais como x+y, 4x, ...
• ${\mathcal {E}}^{2}$ provê todas as funções de multiplicação, tais como xy, x⁴
• ${\mathcal {E}}^{3}$ provê todas as funções exponenciais, tais como x^y, 2^22x, e é exatamente função recursiva elementar.
• ${\mathcal {E}}^{4}$ provê todas as funções de tetração, e assim por diante.

Relação com as funções recursivas primitivas

A definição de ${\mathcal {E}}^{n}$ é a mesma de função recursiva primitiva, RP, exceto que recursão é limitada ($f(t,{\bar {u}})\leq j(t,{\bar {u}})$ para algum j em ${\mathcal {E}}^{n}$) e as funções $(E_{k})_{k<n}$ são explicitamente incluidas em ${\mathcal {E}}^{n}$. 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. ${\mathcal {E}}^{n}\subseteq RP$) e assim:

$\bigcup _{n}{{\mathcal {E}}^{n}}\subseteq RP$

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

$\bigcup _{n}{{\mathcal {E}}^{n}}=RP$

e conjuntos ${\mathcal {E}}^{0},{\mathcal {E}}^{1}-{\mathcal {E}}^{0},{\mathcal {E}}^{2}-{\mathcal {E}}^{1},\dots ,{\mathcal {E}}^{n}-{\mathcal {E}}^{n-1},\dots$ [[partição de conjunto|particiona]] o conjunto de funções recursivas primitivas, PR.

Extensões

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 $E_{\alpha }$ tem que ser recursivamente definida por ordinais limitados (observe que eles já eram recursivamente definidos para ordinais sucessores pela relação $E_{\alpha +1}(n)=E_{\alpha }^{n}(2)$). Se existe uma forma padrão de definir a sequencia fundamental $\lambda _{m}$, cujo ordinal limitado é $\lambda$, então a função geradora pode ser definida como $E_{\lambda }(n)=E_{\lambda _{n}}(n)$. 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 α < ε₀.

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

Bibliografia

• Brainerd, W.S., Landweber, L.H. (1974), Theory of Computation, Wiley, ISBN 0-471-09585-0
• Cichon, E. A.; Wainer, S. S. (1983), «The slow-growing and the Grzegorczyk hierarchies», The Journal of Symbolic Logic, ISSN 0022-4812, 48 (2): 399–408, doi:10.2307/2273557, MR704094 
• Gakwaya, J.–S. (1997), A survey on the Grzegorczyk Hierarchy and its Extension through the BSS Model of Computability
• Grzegorczyk, A. (1953), Some classes of recursive functions, Rozprawy matematyczne, Vol 4, pp. 1–45.
• Löb, M.H. and Wainer, S.S., "Hierarchies of Number Theoretic Functions I, II: A Correction," Arch. Math. Logik Grundlagenforschung 14, 1970 pp. 198–199.
• Rose, H.E., "Subrecursion: Functions and hierarchies", Oxford University Press, New York, USA, 1984. ISBN 0-19-853189-3
• Wagner, K. and Wechsung, G. (1986), Computational Complexity, Mathematics and its Applications v. 21. ISBN 978-90-277-2146-4