Grzegorczykova hierarchie - Grzegorczyk hierarchy

The Grzegorczykova hierarchie (/ɡrɛˈɡ.rtʃək/, Polská výslovnost:[ɡʐɛˈɡɔrt͡ʂɨk]), pojmenovaný podle polského logika Andrzej Grzegorczyk, je hierarchie funkcí používaných v teorie vypočítatelnosti (Wagner a Wechsung 1986: 43). Každý funkce v hierarchii Grzegorczyk je a primitivní rekurzivní funkce a každá primitivní rekurzivní funkce se v hierarchii objeví na určité úrovni. Hierarchie se zabývá rychlostí, s jakou rostou hodnoty funkcí; intuitivně rostou funkce na nižší úrovni hierarchie pomaleji než funkce na vyšších úrovních.

Definice

Nejprve představíme nekonečnou sadu funkcí, označených E_i pro nějaké přirozené číslo i. Definujeme ${displaystyle E_ {0} (x, y) = x + y}$ a ${displaystyle E_ {1} (x) = x ^ {2} +2}$. Tj., E₀ je funkce přidání a E₁ je unární funkce, která umocní svůj argument na druhou a přidá dvě. Pak pro každého n větší než 1, definujeme ${displaystyle E_ {n} (x) = E_ {n-1} ^ {x} (2)}$, tj X-th opakovat z ${displaystyle E_ {n-1}}$ hodnoceno na 2.

Z těchto funkcí definujeme hierarchii Grzegorczyk. ${displaystyle {mathcal {E}} ^ {n}}$, n-tá sada v hierarchii, obsahuje následující funkce:

1. E_k pro k < n
2. nulová funkce (Z(X) = 0);
3. the nástupnická funkce (S(X) = X + 1);
4. the projekční funkce (${displaystyle p_ {i} ^ {m} (t_ {1}, t_ {2}, tečky, t_ {m}) = t_ {i}}$);
5. (zobecněný) složení funkcí v sadě (pokud h, G₁, G₂, ... a G_m jsou v ${displaystyle {mathcal {E}} ^ {n}}$, pak ${displaystyle f ({ar {u}}) = h (g_ {1} ({ar {u}}), g_ {2} ({ar {u}}), tečky, g_ {m} ({ar { u}}))}$ je také)^{[poznámka 1]}; a
6. výsledky omezené (primitivní) rekurze aplikované na funkce v sadě, (pokud G, h a j jsou v ${displaystyle {mathcal {E}} ^ {n}}$ a ${displaystyle f (t, {ar {u}}) leq j (t, {ar {u}})}$ pro všechny t a ${displaystyle {ar {u}}}$, a dál ${displaystyle f (0, {ar {u}}) = g ({ar {u}})}$ a ${displaystyle f (t + 1, {ar {u}}) = h (t, {ar {u}}, f (t, {ar {u}}))}$, pak F je v ${displaystyle {mathcal {E}} ^ {n}}$ také)^{[poznámka 1]}

Jinými slovy, ${displaystyle {mathcal {E}} ^ {n}}$ je uzavření sady ${displaystyle B_ {n} = {Z, S, (p_ {i} ^ {m}) _ {ileq m}, E_ {k}: k$ s ohledem na funkční složení a omezenou rekurzi (jak je definováno výše).

Vlastnosti

Tyto sady jasně tvoří hierarchii

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

protože jsou uzávěry nad ${displaystyle B_ {n}}$a ${displaystyle B_ {0} subseteq B_ {1} subseteq B_ {2} subseteq cdots}$.

Jedná se o přísné podmnožiny (Rose 1984; Gakwaya 1997). Jinými slovy

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

protože hyper operace ${displaystyle H_ {n}}$ je v ${displaystyle {mathcal {E}} ^ {n}}$ ale ne v ${displaystyle {mathcal {E}} ^ {n-1}}$.

• ${displaystyle {mathcal {E}} ^ {0}}$ zahrnuje funkce jako X+1, X+2, ...
• ${displaystyle {mathcal {E}} ^ {1}}$ poskytuje všechny doplňkové funkce, jako je X+y, 4X, ...
• ${displaystyle {mathcal {E}} ^ {2}}$ poskytuje všechny funkce násobení, jako např xy, X⁴
• ${displaystyle {mathcal {E}} ^ {3}}$ poskytuje všechny funkce umocňování, například X^y, 2^22X, a je to přesně základní rekurzivní funkce.
• ${displaystyle {mathcal {E}} ^ {4}}$ poskytuje vše tetování funkce atd.

Pozoruhodně obě funkce ${displaystyle U}$ a charakteristická funkce predikátu ${displaystyle T}$ z Kleene věta o normální formě jsou definovatelné takovým způsobem, že leží na úrovni ${displaystyle {mathcal {E}} ^ {0}}$ hierarchie Grzegorczyk. To zejména znamená, že každá rekurzivně vyčíslitelná množina je některými vyčíslitelná ${displaystyle {mathcal {E}} ^ {0}}$-funkce.

Vztah k primitivním rekurzivním funkcím

Definice ${displaystyle {mathcal {E}} ^ {n}}$ je stejný jako u primitivní rekurzivní funkce, PR, kromě toho, že rekurze je omezený (${displaystyle f (t, {ar {u}}) leq j (t, {ar {u}})}$ pro některé j v ${displaystyle {mathcal {E}} ^ {n}}$) a funkce ${displaystyle (E_ {k}) _ {k$ jsou výslovně zahrnuty v ${displaystyle {mathcal {E}} ^ {n}}$. Na hierarchii Grzegorczyků lze tedy pohlížet jako na cestu omezit moc primitivní rekurze na různé úrovně.

Z této skutečnosti je zřejmé, že všechny funkce na jakékoli úrovni hierarchie Grzegorczyk jsou primitivní rekurzivní funkce (tj. ${displaystyle {mathcal {E}} ^ {n} subseteq {mathsf {PR}}}$) a tudíž:

${displaystyle igcup _ {n} {{mathcal {E}} ^ {n}} subseteq {mathsf {PR}}}$

Lze také ukázat, že všechny primitivní rekurzivní funkce jsou na určité úrovni hierarchie (Rose 1984; Gakwaya 1997), tedy

${displaystyle igcup _ {n} {{mathcal {E}} ^ {n}} = {mathsf {PR}}}$

a sady ${displaystyle {mathcal {E}} ^ {0}, {mathcal {E}} ^ {1} - {mathcal {E}} ^ {0}, {mathcal {E}} ^ {2} - {mathcal {E }} ^ {1}, tečky, {mathcal {E}} ^ {n} - {mathcal {E}} ^ {n-1}, tečky}$ rozdělit množina primitivních rekurzivních funkcí, PR.

Rozšíření

Hierarchii Grzegorczyk lze rozšířit na transfinitní řadové. Taková rozšíření definují a rychle rostoucí hierarchie. K tomu generující funkce ${displaystyle E_ {alpha}}$ musí být rekurzivně definovány pro mezní řadové číslice (všimněte si, že již byly rekurzivně definovány pro nástupní řadové čísly vztahem ${displaystyle E_ {alpha +1} (n) = E_ {alpha} ^ {n} (2)}$). Pokud existuje standardní způsob definování a základní posloupnost ${displaystyle lambda _ {m}}$, jehož mezní pořadové číslo je ${displaystyle lambda}$, pak lze definovat generující funkce ${displaystyle E_ {lambda} (n) = E_ {lambda _ {n}} (n)}$. Tato definice však závisí na standardním způsobu definování základní posloupnosti. Rose (1984) navrhuje standardní způsob pro všechny ordinály α < ε₀.

Původní rozšíření bylo kvůli Martin Löb a Stan S. Wainer (1970) a někdy se mu říká Hierarchie Löb – Wainer.

Viz také

• ZÁKLADNÍ
• Pořadová analýza

Poznámky

Reference

• Brainerd, W.S., Landweber, L.H. (1974), Teorie výpočtuWiley, ISBN  0-471-09585-0
• Cichon, E. A .; Wainer, S. S. (1983), „Pomalu rostoucí a Grzegorczykovy hierarchie“, Journal of Symbolic Logic, 48 (2): 399–408, doi:10.2307/2273557, ISSN  0022-4812, PAN  0704094
• Gakwaya, J.–S. (1997), Průzkum o hierarchii Grzegorczyk a jejím rozšíření prostřednictvím modelu BSS modelu vypočítatelnosti
• Grzegorczyk, A (1953). "Některé třídy rekurzivních funkcí" (PDF). Rozprawy matematyczne. 4: 1–45.
• Löb, M.H .; Wainer, S. S. (1970). „Hierarchie číselně teoretických funkcí I, II: Oprava“. Archiv matematické logiky a Grundlagenforschung. 14: 198–199. doi:10.1007 / bf01991855.
• Rose, HE, Subrekurze: Funkce a hierarchie, Oxford University Press, 1984. ISBN  0-19-853189-3
• Wagner, K. a Wechsung, G. (1986), Výpočetní složitostMatematika a její aplikace v. 21. ISBN  978-90-277-2146-4