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
[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:
- Ek para k < n
- A função zero (Z(x) = 0);
- A função sucessor (S(x) = x + 1);
- A função de projeção ();
- 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
- 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]![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/3a/Magnifying_glass_01.svg/17px-Magnifying_glass_01.svg.png)
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]- ↑ 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]- 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