Hierarquia de Grzegorczyk
A hierarquia Grzegorczyk - nomeada em homenagem ao lógico polonês Andrzej Grzegorczyk - é uma hierarquia de funções usada na teoria da computabilidade . Todas as funções da hierarquia Grzegorczyk são primitivas recursivas e qualquer função primitiva recursiva aparece nesta hierarquia. Essa hierarquia classifica as funções de acordo com seu crescimento. Intuitivamente, as funções de um nível crescem menos rapidamente do que as funções dos níveis superiores.
Definição
Em primeiro lugar, introduzimos um conjunto infinito de funções notadas para qualquer número natural .
Eeu{\ displaystyle E_ {i}}eu{\ displaystyle i}
Nós posamos e . Em outras palavras, é a função de adição e é uma função unária que eleva ao quadrado seu argumento e adiciona .
E0:(x,y)↦x+y{\ displaystyle E_ {0} :( x, y) \ mapsto x + y}E1:x↦x2+2{\ displaystyle E_ {1}: x \ mapsto x ^ {2} +2}E0{\ displaystyle E_ {0}}E1{\ displaystyle E_ {1}}2{\ displaystyle 2}
Então, para o todo , definimos
não⩾2{\ displaystyle n \ geqslant 2}
Enão:x↦{2E se x=0Enão-1(Enão(x-1))se não{\ displaystyle E_ {n}: x \ mapsto {\ begin {cases} 2 & {\ text {si}} x = 0 \\ E_ {n-1} (E_ {n} (x-1)) & { \ text {caso contrário}} \ end {casos}}}Podemos então definir a hierarquia de Grzegorczyk. , O N classe -ésimo (ou nível) da hierarquia de grzegorczyk é o mais pequeno conjunto que contenha
Enão{\ displaystyle {\ mathcal {E}} ^ {n}}
-
Ek{\ displaystyle E_ {k}}para ,k<não{\ displaystyle k <n}
- a função nula,
- a função sucessora ( ),S(x)=x+1{\ displaystyle S (x) = x + 1}
- projeções ( ),peum(t1,t2,...,tm)=teu{\ displaystyle p_ {i} ^ {m} (t_ {1}, t_ {2}, \ ldots, t_ {m}) = t_ {i}}
e estável por
- composição baseada (se , , , ..., são funções de , então assim é)f{\ displaystyle f}g1{\ displaystyle g_ {1}}g2{\ displaystyle g_ {2}}gm{\ displaystyle g_ {m}}Enão{\ displaystyle {\ mathcal {E}} ^ {n}}f(você¯)=h(g1(você¯),g2(você¯),...,gm(você¯)){\ displaystyle f ({\ bar {u}}) = h (g_ {1} ({\ bar {u}}), g_ {2} ({\ bar {u}}), \ dots, g_ {m } ({\ bar {u}}))}
- recursão limitada, (se , e são funções de e isso é tal que , e , então também é uma função de ).g{\ displaystyle g}h{\ displaystyle h}j{\ displaystyle j}Enão{\ displaystyle {\ mathcal {E}} ^ {n}}f{\ displaystyle f}∀t,∀você¯,f(t,você¯)⩽j(t,você¯){\ displaystyle \ forall t, \ forall {\ bar {u}}, f (t, {\ bar {u}}) \ leqslant j (t, {\ bar {u}})}f(0,você¯)=g(você¯){\ displaystyle f (0, {\ bar {u}}) = g ({\ bar {u}})}f(t+1,você¯)=h(t,você¯,f(t,você¯)){\ displaystyle f (t + 1, {\ bar {u}}) = h (t, {\ bar {u}}, f (t, {\ bar {u}}))}f{\ displaystyle f}Enão{\ displaystyle {\ mathcal {E}} ^ {n}}
Propriedades
Nós temos
E0⊆E1⊆E2⊆⋯{\ displaystyle {\ mathcal {E}} ^ {0} \ subseteq {\ mathcal {E}} ^ {1} \ subseteq {\ mathcal {E}} ^ {2} \ subseteq \ cdots}desde então .
{Ek∣k<0}⊆{Ek∣k<1}⊆{Ek∣k<2}⊆⋯{\ displaystyle \ {E_ {k} \ mid k <0 \} \ subseteq \ {E_ {k} \ mid k <1 \} \ subseteq \ {E_ {k} \ mid k <2 \} \ subseteq \ cdots }
Na verdade, a inclusão é estrita (Rose 1984; Gakwaya 1997)
E0⊊E1⊊E2⊊⋯{\ displaystyle {\ mathcal {E}} ^ {0} \ subsetneq {\ mathcal {E}} ^ {1} \ subsetneq {\ mathcal {E}} ^ {2} \ subsetneq \ cdots}porque a hiperoperação pertence a, mas não pertence .
Hnão{\ displaystyle H_ {n}}Enão{\ displaystyle {\ mathcal {E}} ^ {n}}Enão-1{\ displaystyle {\ mathcal {E}} ^ {n-1}}
-
E0{\ displaystyle {\ mathcal {E}} ^ {0}}contém funções, tais como , , ,x↦x{\ displaystyle x \ mapsto x}x↦x+1{\ displaystyle x \ mapsto x + 1}x↦x+2{\ displaystyle x \ mapsto x + 2}
-
E1{\ displaystyle {\ mathcal {E}} ^ {1}}contém todas as funções tais como a adição , ,x↦4x{\ displaystyle x \ mapsto 4x}(x,y)↦x+y{\ displaystyle (x, y) \ mapsto x + y}
-
E2{\ displaystyle {\ mathcal {E}} ^ {2}}contém as funções de multiplicação, tais como , ,(x,y)↦xy{\ displaystyle (x, y) \ mapsto xy}x↦x4{\ displaystyle x \ mapsto x ^ {4}}
-
E3{\ displaystyle {\ mathcal {E}} ^ {3}}exponenciação contém funções, como , . Este conjunto é igual ao das funções elementares ,(x,y)↦xy{\ displaystyle (x, y) \ mapsto x ^ {y}}x↦222x{\ displaystyle x \ mapsto 2 ^ {2 ^ {2 ^ {x}}}}
-
E4{\ displaystyle {\ mathcal {E}} ^ {4}}contém tetration .
Relação com funções primitivas recursivas
A definição de é a mesma das funções recursivas primitivas , exceto que a construção recursiva é limitada ( para uma determinada função ) e as funções estão claramente incluídas em . Portanto, a hierarquia Grzegorczyk pode ser vista como uma forma de limitar o poder da recursão primitiva.
Enão{\ displaystyle {\ mathcal {E}} ^ {n}}PR{\ displaystyle PR}f(t,você¯)≤j(t,você¯){\ displaystyle f (t, {\ bar {u}}) \ leq j (t, {\ bar {u}})}j∈Enão{\ displaystyle j \ in {\ mathcal {E}} ^ {n}}(Ek)k<não{\ displaystyle (E_ {k}) _ {k <n}}Enão{\ displaystyle {\ mathcal {E}} ^ {n}}
É claro que as funções de cada nível são primitivas recursivas (ou seja ) e, portanto,
Enão⊆PR{\ displaystyle {\ mathcal {E}} ^ {n} \ subseteq PR}
⋃nãoEnão⊆PR{\ displaystyle \ bigcup _ {n} {{\ mathcal {E}} ^ {n}} \ subseteq PR}Também podemos mostrar que qualquer função primitiva recursiva está presente na hierarquia de Grzegorczyk (Rose 1984; Gakwaya 1997).
⋃nãoEnão=PR{\ displaystyle \ bigcup _ {n} {{\ mathcal {E}} ^ {n}} = PR}e os conjuntos formam uma partição do conjunto de funções primitivas recursivas .
E0,E1∖E0,E2∖E1,...,Enão∖Enão-1,...{\ displaystyle {\ mathcal {E}} ^ {0}, {\ mathcal {E}} ^ {1} \ setminus {\ mathcal {E}} ^ {0}, {\ mathcal {E}} ^ {2 } \ setminus {\ mathcal {E}} ^ {1}, \ dots, {\ mathcal {E}} ^ {n} \ setminus {\ mathcal {E}} ^ {n-1}, \ ldots}PR{\ displaystyle PR}
Extensões
A hierarquia Grzegorczyk pode ser estendida para ordinais transfinitos . Em seguida, definimos a hierarquia de crescimento rápido . Para isso, a definição de deve ser estendida para ordinais limite, pois eles já estão definidos para ordinais sucessores por . Se houver um método padrão de definição de uma sequência fundamental cujo limite ordinal é , a geração dessas funções pode ser definida como . No entanto, esta definição depende da seqüência fundamental. Rose (1984) propõe um método padrão para qualquer ordinal .
Eα{\ displaystyle E _ {\ alpha}}Eα+1(não)=Eαnão(2){\ displaystyle E _ {\ alpha +1} (n) = E _ {\ alpha} ^ {n} (2)} λm{\ displaystyle \ lambda _ {m}}λ{\ displaystyle \ lambda}Eλ(não)=Eλnão(não){\ displaystyle E _ {\ lambda} (n) = E _ {\ lambda _ {n}} (n)}α<ε0{\ displaystyle \ alpha <\ varepsilon _ {0}}
A extensão original é devida a Martin Löb e Stan S. Wainer (1970) e às vezes é chamada de hierarquia Löb - Wainer.
Bibliografia
- Brainerd, WS, Landweber, LH (1974), Theory of Computation , Wiley, ( ISBN 0-471-09585-0 )
- Gakwaya, J.–S. (1997), Um levantamento sobre a Hierarquia de Grzegorczyk e sua Extensão através do Modelo BSS de Computabilidade
- Grzegorczyk, A. (1953), Some classes of recursive functions , Rozprawy matematyczne, Vol 4, p. 1-45 .
- Löb, MH e Wainer, SS, "Hierarchies of Number Theoretic Functions I, II: A Correction," Arch. Matemática. Logik Grundlagenforschung 14, 1970 p. 198-199 .
- Rose, HE, "Subrecursion: Functions and hierarchies", Oxford University Press, New York, USA, 1984. ( ISBN 0-19-853189-3 )
- Wagner, K. e Wechsung, G. (1986), Computational Complexity , Mathematics and its Applications v. 21. ( ISBN 978-90-277-2146-4 )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">