Grzegorczyk Hierarchie

Das Grzegorczyk Hierarchie (/ɡrɛˈɡɔːrtʃək/, Polnische Aussprache:[ʐɛˈʐɛˈɔrt͡ʂɨk]), benannt nach dem polnischen Logiker Andrzej Grzegorczykist eine Hierarchie von Funktionen, die in verwendet werden Computerbarkeitstheorie (Wagner und Wechsung 1986: 43). Jeder Funktion In der Grzegorczyk -Hierarchie ist a primitive rekursive Funktionund jede primitive rekursive Funktion erscheint in der Hierarchie auf einer bestimmten Ebene. Die Hierarchie befasst sich mit der Rate, mit der die Werte der Funktionen wachsen; Intuitiv werden die Funktionen in niedrigeren Ebenen der Hierarchie langsamer als Funktionen in den höheren Ebenen.

Definition

Zuerst stellen wir eine unendliche Reihe von Funktionen ein, die bezeichnet werden E_i für einige natürliche Zahl i. Wir definieren ${\ displayStyle e_ {0} (x, y) = x+y}$ und ${\ displayStyle e_ {1} (x) = x^{2} +2}$. D.h. E₀ ist die Additionsfunktion und E₁ ist eine unäre Funktion, die ihre Argumentation aufschlägt und zwei hinzugefügt wird. Dann für jeden n Mehr als 2 definieren wir ${\ displayStyle e_ {n} (x) = e_ {n-1}^{x} (2)}$, d.h. die x-Th iterieren von ${\ displayStyle e_ {n-1}}$ bewertet bei 2.

Aus diesen Funktionen definieren wir die Grzegorczyk -Hierarchie. ${\ displaystyle {\ mathcal {e}}^{n}}$, das n-Die in der Hierarchie enthält die folgenden Funktionen:

1. E_k zum k < n
2. die Nullfunktion (Z(x) = 0);
3. das Nachfolgerfunktion (S(x) = x + 1);
4. das Projektionsfunktionen (${\ displaystyle p_ {i}^{m} (t_ {1}, t_ {2}, \ dots, t_ {m}) = t_ {i}}$);
5. das (verallgemeinerte) Kompositionen von Funktionen im Set (wenn h, g₁, g₂, ... und g_m sind in ${\ displaystyle {\ mathcal {e}}^{n}}$, dann ${\ displayStyle f ({\ bar {u}}) = h (g_ {1} ({\ bar {u}}), g_ {2} ({\ bar {u}}), \ dots, g_ {m } ({\ bar {u}}))}$ ist auch)^{[Anmerkung 1]}; und
6. Die Ergebnisse der begrenzten (primitiven) Rekursion, die auf Funktionen im Satz angewendet wird (wenn g, h und j sind in ${\ displaystyle {\ mathcal {e}}^{n}}$ und ${\ displayStyle f (t, {\ bar {u}}) \ leq j (t, {\ bar {u}})}$ für alle t und ${\ displayStyle {\ bar {u}}}$, und weiter ${\ displayStyle f (0, {\ bar {u}}) = g ({\ bar {u}})}$ und ${\ displayStyle f (t+1, {\ bar {u}}) = h (t, {\ bar {u}}, f (t, {\ bar {u}})}}$, dann f ist in ${\ displaystyle {\ mathcal {e}}^{n}}$ auch)^{[Anmerkung 1]}

Mit anderen Worten, ${\ displaystyle {\ mathcal {e}}^{n}}$ ist der Schließung of set $oder$ in Bezug auf Funktionszusammensetzung und begrenzte Rekursion (wie oben definiert).

Eigenschaften

Diese Sätze bilden eindeutig die Hierarchie

${\ displayStyle {\ mathcal {e}}^{0} \ subseteq {\ mathcal {e}}^{1} \ subseteq {\ mathcal {e}}^{2} \ subseteq \ cdots}}}}$

Weil sie Schließungen über dem sind ${\ displayStyle b_ {n}}$und $oder$.

Sie sind strenge Untergruppen (Rose 1984; Gakwaya 1997). Mit anderen Worten

${\ displaystyle {\ mathcal {e}}^{0} \ subsetneq {\ mathcal {e}}^{1} \ subsetneq {\ mathcal {e}}^{2} \ subetneq \ cdots}}}}$

weil die Hyperbetrieb ${\ displayStyle H_ {n}}$ ist in ${\ displaystyle {\ mathcal {e}}^{n}}$ aber nicht in ${\ displayStyle {\ mathcal {e}}^{n-1}}$.

• ${\ displayStyle {\ mathcal {e}}^{0}}$ beinhaltet Funktionen wie z. x+1, x+2, ...
• ${\ displayStyle {\ mathcal {e}}^{1}}$ Bietet alle Additionsfunktionen, wie z. x+y, 4x, ...
• ${\ displayStyle {\ mathcal {e}}^{2}}$ Bietet alle Multiplikationsfunktionen, wie z. xy, x⁴
• ${\ displaystyle {\ mathcal {e}}^{3}}$ Bietet alle Exponentiationsfunktionen, wie z. x^y, 2^22xund ist genau das elementare rekursive Funktionen.
• ${\ displayStyle {\ mathcal {e}}^{4}}$ Bietet alles Tetation Funktionen und so weiter.

Bemerkenswerterweise sowohl die Funktion ${\ displayStyle u}$ und die charakteristische Funktion des Prädikats ${\ displayStyle t}$ von dem Kleene Normal Form Theorem sind in gewisser Weise definierbar, dass sie auf Ebene liegen ${\ displayStyle {\ mathcal {e}}^{0}}$ der Grzegorczyk -Hierarchie. Dies bedeutet insbesondere, dass jeder aufzählbare Set von einigen aufzählbar ist ${\ displayStyle {\ mathcal {e}}^{0}}$-Funktion.

Beziehung zu primitiven rekursiven Funktionen

Die Definition von ${\ displaystyle {\ mathcal {e}}^{n}}$ ist dasselbe wie das der des primitive rekursive Funktionen, Pr, außer dass die Rekursion ist begrenzt (${\ displayStyle f (t, {\ bar {u}}) \ leq j (t, {\ bar {u}})}$ für einige j in ${\ displaystyle {\ mathcal {e}}^{n}}$) und die Funktionen ${\ displayStyle (e_ {k}) _ {k <n}}$ sind explizit in enthalten in ${\ displaystyle {\ mathcal {e}}^{n}}$. Somit kann die Grzegorczyk -Hierarchie als Weg gesehen werden Grenze Die Kraft der primitiven Rekursion auf verschiedene Ebenen.

Aus dieser Tatsache geht hervor, dass alle Funktionen in jeder Ebene der Grzegorczyk -Hierarchie primitive rekursive Funktionen sind (d. H. ${\ displaystyle {\ mathcal {e}}^{n} \ subseteq {\ mathsf {pr}}}$) und somit:

$oder$

Es kann auch gezeigt werden, dass sich alle primitiven rekursiven Funktionen in einer gewissen Ebene der Hierarchie befinden (Rose 1984; Gakwaya 1997), somit

${\ displaystyle \ bigcup _ {n} {{\ mathcal {e}}^{n}} = {\ mathsf {pr}}}$

und die Sets ${\ displaystyle {\ mathcal {e}}^{0}, {\ mathcal {e}}^{1}-{\ mathcal {e}}^{0}, {\ mathcal {e} {2} {2} -{\ mathcal {e}}^{1}, \ dots, {\ mathcal {e}}^{n}-{\ mathcal {e}}^{n-1}, \ dots}$ Trennwand die Menge der primitiven rekursiven Funktionen, Pr.

Erweiterungen

Die Grzegorczyk -Hierarchie kann erweitert werden transfinite Ordinale. Solche Erweiterungen definieren a schnell wachsende Hierarchie. Dazu die Erzeugungsfunktionen ${\ displayStyle e _ {\ alpha}}$ muss rekursiv für Grenzbestimmungen definiert werden (beachten Sie, dass sie bereits für Nachfolgerverordnungen durch die Beziehung rekursiv definiert wurden ${\ displayStyle e _ {\ alpha +1} (n) = e _ {\ alpha}^{n} (2)}$). Wenn es eine Standardmethode gibt, um a zu definieren Grundsequenz ${\ displaystyle \ lambda _ {m}}$, Deren Ordinal begrenzen ist ${\ displayStyle \ lambda}$und dann können die Erzeugungsfunktionen definiert werden ${\ displayStyle e _ {\ lambda} (n) = e _ {\ lambda _ {n}} (n)}$. Diese Definition hängt jedoch von einer Standardmethode ab, um die grundlegende Sequenz zu definieren. Rose (1984) schlägt eine Standardmethode für alle Ordnungen vor α < ε₀.

Die ursprüngliche Erweiterung war auf Martin Löb und Stan S. Wainer (1970) und manchmal genannt das Löb -Wainer -Hierarchie.

Siehe auch

• Elementar
• Ordinale Analyse

Anmerkungen

Verweise

• Brainerd, W. S., Landweber, L. H. (1974), Theorie der Berechnung, Wiley, ISBN0-471-09585-0
• Cichon, E. A.; Wainer, S. S. (1983), "Der langsam wachsende und die Grzegorczyk-Hierarchien", Zeitschrift für symbolische Logik, 48 (2): 399–408, doi:10.2307/2273557, ISSN 0022-4812, HERR 0704094
• Gakwaya, J. - S. (1997),, Eine Umfrage zur Grzegorczyk -Hierarchie und ihre Erweiterung durch das BSS -Modell der Computerbarkeit
• Grzegorczyk, A (1953). "Einige Klassen rekursiver Funktionen" (PDF). Rozprawy Matematyczne. 4: 1–45.
• Löb, M.H.;Wainer, S. S. (1970)."Hierarchien der theoretischen Funktionen I, II: Eine Korrektur". Archiv für Mathematische Logik und GrundlagenforSchung. 14: 198–199. doi:10.1007/bf01991855.
• Rose, H.E., Unterrezidier: Funktionen und Hierarchien, Oxford University Press, 1984. ISBN0-19-853189-3
• Wagner, K. und Wechsung, G. (1986), Rechenkomplexität, Mathematik und seine Anwendungen gegen 21. ISBN978-90-277-2146-4