Grzegorczyk hierarki

Den Grzegorczyk hierarki - oppkalt etter polske logician Andrzej Grzegorczyk - er et hierarki av funksjoner som brukes i computability teori . Alle funksjonene til Grzegorczyk-hierarkiet er rekursive primitiver, og enhver rekursiv primitiv funksjon vises i dette hierarkiet. Dette hierarkiet klassifiserer funksjoner i henhold til veksten. Intuitivt vokser funksjonene til ett nivå mindre raskt enn funksjonene på de høyere nivåene.

Definisjon

Først og fremst introduserer vi et uendelig sett med funksjoner som er kjent for et naturlig tall . EJeg{\ displaystyle E_ {i}}Jeg{\ displaystyle i}

Vi stiller og . Med andre ord er tilleggsfunksjonen og er en unarisk funksjon som kvadrerer argumentet og legger til . 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}

Så definerer vi for det heleikke⩾2{\ displaystyle n \ geqslant 2}

Eikke:x↦{2hvis x=0Eikke-1(Eikke(x-1))Hvis ikke{\ displaystyle E_ {n}: x \ mapsto {\ begin {cases} 2 & {\ text {si}} x = 0 \\ E_ {n-1} (E_ {n} (x-1)) & { \ text {ellers}} \ end {cases}}}

Vi kan da definere hierarkiet til Grzegorczyk. , er n- klasse (eller nivå) i Grzegorczyk-hierarkiet det minste settet som inneholder Eikke{\ displaystyle {\ mathcal {E}} ^ {n}}

1. Ek{\ displaystyle E_ {k}}for ,k<ikke{\ displaystyle k <n}
2. null-funksjonen,
3. den etterfølgende funksjon ( ),S(x)=x+1{\ displaystyle S (x) = x + 1}
4. anslag ( ),sJegm(t1,t2,...,tm)=tJeg{\ displaystyle p_ {i} ^ {m} (t_ {1}, t_ {2}, \ ldots, t_ {m}) = t_ {i}}

og stabil av

1. baserte preparat (hvis , , , ..., er funksjoner av , da så er)f{\ displaystyle f}g1{\ displaystyle g_ {1}}g2{\ displaystyle g_ {2}}gm{\ displaystyle g_ {m}}Eikke{\ displaystyle {\ mathcal {E}} ^ {n}}f(u¯)=h(g1(u¯),g2(u¯),...,gm(u¯)){\ displaystyle f ({\ bar {u}}) = h (g_ {1} ({\ bar {u}}), g_ {2} ({\ bar {u}}), \ prikker, g_ {m } ({\ bar {u}}))}
2. begrenset rekursjon, (hvis , og er funksjoner av og det er slik at , og , da er også en funksjon av ).g{\ displaystyle g}h{\ displaystyle h}j{\ displaystyle j}Eikke{\ displaystyle {\ mathcal {E}} ^ {n}}f{\ displaystyle f}∀t,∀u¯,f(t,u¯)⩽j(t,u¯){\ displaystyle \ forall t, \ forall {\ bar {u}}, f (t, {\ bar {u}}) \ leqslant j (t, {\ bar {u}})}f(0,u¯)=g(u¯){\ displaystyle f (0, {\ bar {u}}) = g ({\ bar {u}})}f(t+1,u¯)=h(t,u¯,f(t,u¯)){\ displaystyle f (t + 1, {\ bar {u}}) = h (t, {\ bar {u}}, f (t, {\ bar {u}}))}f{\ displaystyle f}Eikke{\ displaystyle {\ mathcal {E}} ^ {n}}

Eiendommer

Vi har

E0⊆E1⊆E2⊆⋯{\ displaystyle {\ mathcal {E}} ^ {0} \ subseteq {\ mathcal {E}} ^ {1} \ subseteq {\ mathcal {E}} ^ {2} \ subseteq \ cdots}

siden . {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 }

Faktisk er inkluderingen streng (Rose 1984; Gakwaya 1997)

E0⊊E1⊊E2⊊⋯{\ displaystyle {\ mathcal {E}} ^ {0} \ subsetneq {\ mathcal {E}} ^ {1} \ subsetneq {\ mathcal {E}} ^ {2} \ subsetneq \ cdots}

fordi hyperoperasjonen tilhører, men ikke til . Hikke{\ displaystyle H_ {n}}Eikke{\ displaystyle {\ mathcal {E}} ^ {n}}Eikke-1{\ displaystyle {\ mathcal {E}} ^ {n-1}}

• E0{\ displaystyle {\ mathcal {E}} ^ {0}}inneholder funksjoner som , , ,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}}inneholder alle de funksjoner som addisjon , ,x↦4x{\ displaystyle x \ mapsto 4x}(x,y)↦x+y{\ displaystyle (x, y) \ mapsto x + y}
• E2{\ displaystyle {\ mathcal {E}} ^ {2}}inneholder gange funksjoner, for eksempel , ,(x,y)↦xy{\ displaystyle (x, y) \ mapsto xy}x↦x4{\ displaystyle x \ mapsto x ^ {4}}
• E3{\ displaystyle {\ mathcal {E}} ^ {3}}inneholder potenser funksjoner, som , . Dette settet er lik det for de grunnleggende funksjonene ,(x,y)↦xy{\ displaystyle (x, y) \ mapsto x ^ {y}}x↦222x{\ displaystyle x \ mapsto 2 ^ {2 ^ {2 ^ {x}}}}
• E4{\ displaystyle {\ mathcal {E}} ^ {4}}inneholder tetrasjon .

Forholdet til rekursive primitive funksjoner

Definisjonen av er den samme som for de primitive rekursive funksjonene , bortsett fra at den rekursive konstruksjonen er avgrenset ( for en bestemt funksjon ) og funksjonene er tydelig inkludert i . Derfor kan Grzegorczyk-hierarkiet sees på som en måte å begrense kraften til primitiv rekursjon. Eikke{\ displaystyle {\ mathcal {E}} ^ {n}}PR{\ displaystyle PR}f(t,u¯)≤j(t,u¯){\ displaystyle f (t, {\ bar {u}}) \ leq j (t, {\ bar {u}})}j∈Eikke{\ displaystyle j \ i {\ mathcal {E}} ^ {n}}(Ek)k<ikke{\ displaystyle (E_ {k}) _ {k <n}}Eikke{\ displaystyle {\ mathcal {E}} ^ {n}}

Det er klart at funksjonene til hvert nivå er rekursive primitiver (dvs. ) og derfor Eikke⊆PR{\ displaystyle {\ mathcal {E}} ^ {n} \ subseteq PR}

⋃ikkeEikke⊆PR{\ displaystyle \ bigcup _ {n} {{\ mathcal {E}} ^ {n}} \ subseteq PR}

Vi kan også vise at en hvilken som helst rekursiv primitiv funksjon er tilstede i hierarkiet til Grzegorczyk (Rose 1984; Gakwaya 1997) enten

⋃ikkeEikke=PR{\ displaystyle \ bigcup _ {n} {{\ mathcal {E}} ^ {n}} = PR}

og settene danner en partisjon av settet med rekursive primitive funksjoner . E0,E1∖E0,E2∖E1,...,Eikke∖Eikke-1,...{\ displaystyle {\ mathcal {E}} ^ {0}, {\ mathcal {E}} ^ {1} \ setminus {\ mathcal {E}} ^ {0}, {\ mathcal {E}} ^ {2 } \ setminus {\ mathcal {E}} ^ {1}, \ prikker, {\ mathcal {E}} ^ {n} \ setminus {\ mathcal {E}} ^ {n-1}, \ ldots}PR{\ displaystyle PR}

Utvidelser

Grzegorczyk-hierarkiet kan utvides til transfinite ordinals . Vi definerer deretter hierarkiet med rask vekst . For dette må definisjonen av utvides for grenseverdier, de er faktisk allerede definert for etterfølgere . Hvis det er en standard metode for å definere en grunnleggende sekvens hvis ordinale grense er, kan genereringen av disse funksjonene defineres som . Denne definisjonen avhenger imidlertid av den grunnleggende sekvensen. Rose (1984) foreslår en standardmetode for enhver ordinal . Eα{\ displaystyle E _ {\ alpha}}Eα+1(ikke)=Eαikke(2){\ displaystyle E _ {\ alpha +1} (n) = E _ {\ alpha} ^ {n} (2)} λm{\ displaystyle \ lambda _ {m}}λ{\ displaystyle \ lambda}Eλ(ikke)=Eλikke(ikke){\ displaystyle E _ {\ lambda} (n) = E _ {\ lambda _ {n}} (n)}α<ε0{\ displaystyle \ alpha <\ varepsilon _ {0}}

Den opprinnelige utvidelsen skyldes Martin Löb og Stan S. Wainer (1970) og blir noen ganger referert til som Löb - Wainer-hierarkiet.

Bibliografi

• Brainerd, WS, Landweber, LH (1974), Theory of Computation , Wiley, ( ISBN  0-471-09585-0 )
• Gakwaya, J.–S. (1997), en undersøkelse om Grzegorczyk-hierarkiet og dets utvidelse gjennom BSS-modellen for beregnbarhet
• Grzegorczyk, A. (1953), Noen klasser av rekursive funksjoner , Rozprawy matematyczne, Vol 4, s.  1–45 .
• Löb, MH og Wainer, SS, "Hierarchies of Number Theoretic Functions I, II: A Correction," Arch. Matte. Logik Grundlagenforschung 14, 1970 s.  198–199 .
• Rose, HE, "Subrecursion: Functions and hierarchies", Oxford University Press, New York, USA, 1984. ( ISBN  0-19-853189-3 )
• Wagner, K. og 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;">