Mostrar código-fonte de Hierarquia de Grzegorczyk

{{Sem notas|data=dezembro de 2024}}
A '''hierarquia de Grzegorczyk''' (pronúncia: {{IPAc-pl|g|rz|e|'|g|o|r|cz|y|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 (matemática)|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<sub>i</sub>'' para algum número natural ''i''. Definimos <math>E_0(x,y)=x+y</math> e <math>E_1(x)=x^2+2</math>, i.e, ''E<sub>0</sub>'' é a função adicional, e ''E<sub>1</sub>'' é uma função unária que eleva seus argumentos ao quadrado e soma dois. Depois, para cada ''n'' maior que 1, definimos <math>E_n(x)=E^{x}_{n-1}(2)</math>.

Dessas funções definimos a hierarquia de Grzegorczy. <math>\mathcal{E}^n</math>, o ''n''-ésimo conjunto de hierarquias, contém as seguintes funções:
# ''E<sub>k</sub>'' para ''k'' < ''n''
# A função zero (''Z''(''x'') = 0);
# A [[função sucessor]] (''S''(''x'') = ''x'' + 1);
# A [[função projeção|função de projeção]] (<math> p_i^m(t_1, t_2, \dots, t_m) = t_i </math>);
# A [[composição de funções]] (generalizada) no conjunto (se ''h'', ''g''<sub>1</sub>, ''g''<sub>2</sub>, ... e ''g''<sub>m</sub>  estão em <math>\mathcal{E}^n</math>, então <math> f(\bar{u}) = h(g_1(\bar{u}), g_2(\bar{u}), \dots, g_m(\bar{u})) </math> também estão)<ref group="Perceba" name="tuple notation" />; e 
# O resultado da recursão limitada (primitiva) aplicada a funções no conjunto, (se ''g'', ''h'' e ''j'' estão em <math>\mathcal{E}^n</math> e <math>f(t, \bar{u}) \leq j(t, \bar{u})</math> para todo ''t'' e <math>\bar{u}</math>, e mais <math>f(0, \bar{u}) = g(\bar{u})</math> e <math>f(t+1, \bar{u}) = h(t,\bar{u},f(t,\bar{u}))</math>, então ''f'' está em <math>\mathcal{E}^n</math> também)<ref group="Perceba" name="tuple notation" />

Em outras palavras, <math>\mathcal{E}^n</math> é o [[fechamento]] do conjunto <math>B_n = \{Z, S, (p_i^m)_{i \le m}, E_k : k < n\}</math> com respeito a composição de funções e recursão limitada (como definido acima).

== Propriedades ==

Esses conjuntos claramente são da hierarquia
:<math> \mathcal{E}^0 \subseteq \mathcal{E}^1 \subseteq \mathcal{E}^2 \subseteq \cdots </math>
porque eles são fechados sob a <math>B_n</math>'s e <math> B_0 \subseteq B_1 \subseteq B_2 \subseteq \cdots</math>. 

Eles são subconjuntos próprios (Rose 1984; Gakwaya 1997). Em outras palavras
:<math> \mathcal{E}^0 \subsetneq \mathcal{E}^1 \subsetneq \mathcal{E}^2 \subsetneq \cdots </math>
porque a [[hiperoperação]] <math>H_n</math> está em <math>\mathcal{E}^n</math> mas não em <math>\mathcal{E}^{n-1}</math>.

*<math>\mathcal{E}^0</math> inclui funções como ''x''+1, ''x''+2, ... 
*<math>\mathcal{E}^1</math> provê todas as funções adicionais, tais como ''x''+''y'', 4''x'', ...
*<math>\mathcal{E}^2</math> provê todas as funções de multiplicação, tais como ''xy'', ''x''<sup>4</sup> 
*<math>\mathcal{E}^3</math> provê todas as funções exponenciais, tais como ''x''<sup>''y''</sup>, 2<sup>2<sup>2<sup>''x''</sup></sup></sup>, e é exatamente [[função recursiva elementar]].
*<math>\mathcal{E}^4</math> provê todas as funções de [[tetração]], e assim por diante.

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

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

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
:<math> \bigcup_n{\mathcal{E}^n} = RP </math>
e conjuntos <math> \mathcal{E}^0, \mathcal{E}^1 - \mathcal{E}^0, \mathcal{E}^2 - \mathcal{E}^1, \dots, \mathcal{E}^n - \mathcal{E}^{n-1}, \dots </math> 
<nowiki>[[partição de conjunto|particiona]]</nowiki> o conjunto de funções recursivas primitivas, ''PR''.


== Extensões ==
{{principal|Hierarquia de crescimento rápido}}

A hierarquia de Grzegorczyk  pode ser estendida para [[número ordinal|ordinal]] [[número transfinito|transfinito]].  Tal extensão define uma [[hierarquia de crescimento rápido]].
Para fazer isso, as funções geradoras <math>E_\alpha</math> tem que ser recursivamente definida por ordinais limitados (observe que eles já eram recursivamente definidos para ordinais sucessores pela relação <math> E_{\alpha+1}(n) = E_\alpha^n(2) </math>). Se existe uma forma padrão de definir a ''sequencia fundamental''
<math>\lambda_m</math>, cujo [[ordinal limitado]] é <math>\lambda</math>, então a [[função geradora]] pode ser definida como <math> E_\lambda(n) = E_{\lambda_n}(n) </math>. 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 α < [[epsilon naught|ε<sub>0</sub>]].

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 ==
{{reflist|group=Perceba|refs=

<ref name="tuple notation">Perceba: Aqui <math>\bar{u}</math> representa uma [[tupla]] de entrada para ''f''. A notação <math>f(\bar{u})</math> significa que ''f''aceita algum[[arity|número de argumento]] arbitrário e se <math>\bar{u} = (x, y, z)</math>, então <math>f(\bar{u}) = f(x, y, z)</math>. Na notação <math>f(t, \bar{u})</math>, o primeiro argumento, ''t'', é especificamente explicitado e o resto é uma tupla arbitrária <math>\bar{u}</math>. assim, se <math>\bar{u} = (x, y, z)</math>, então <math>f(t, \bar{u}) = f(t, x, y, z)</math>. Esta notação permite a composição e recursão limitada serem definidas por funções, ''f'', com qualquer número de argumentos.</ref>
}}

== Bibliografia ==
* Brainerd, W.S., Landweber, L.H. (1974), ''Theory of Computation'', Wiley, ISBN 0-471-09585-0
*{{Citation | last1=Cichon | first1=E. A. | last2=Wainer | first2=S. S. | title=The slow-growing and the Grzegorczyk hierarchies | doi=10.2307/2273557 | id={{MathSciNet | id = 704094}} | year=1983 | journal=The Journal of Symbolic Logic | issn=0022-4812 | volume=48 | issue=2 | pages=399–408}}
* Gakwaya, J.–S. (1997), [http://citeseer.ist.psu.edu/gakwaya97survey.html ''A survey on the Grzegorczyk Hierarchy and its Extension through the BSS Model of Computability'']
* Grzegorczyk, A. (1953), [http://matwbn.icm.edu.pl/ksiazki/rm/rm04/rm0401.pdf ''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

{{Classes de complexidade}} 

{{Números muito grandes}}

[[Categoria:Lógica matemática]]
[[Categoria:Hierarquia]]
[[Categoria:Teoria da computabilidade]]