Ierarhia lui Grzegorczyk

Grzegorczyk ierarhie - numit după logician polonez Andrzej Grzegorczyk - este o ierarhie a funcțiilor utilizate în teoria calculabilitate . Toate funcțiile ierarhiei Grzegorczyk sunt primitive recursive și orice funcție primitivă recursivă apare în această ierarhie. Această ierarhie clasifică funcțiile în funcție de creșterea lor. Intuitiv, funcțiile unui nivel cresc mai puțin rapid decât funcțiile nivelurilor superioare.

Definiție

În primul rând, introducem un set infinit de funcții notate pentru orice număr natural . $E_i$ $eu$

Noi pozăm și . Cu alte cuvinte, este funcția de adunare și este o funcție unară care pătrează argumentul și adaugă . $E_ {0} :( x, y) \ mapsto x + y$ $E_ {1}: x \ mapsto x ^ {2} +2$ $E_0$ $E_1$ $2$

Apoi, în ansamblu , definim $n \ geqslant 2$

E_ {n}: x \ mapsto {\ begin {cases} 2 & {\ text {si}} x = 0 \\ E _ {{n-1}} (E_ {n} (x-1)) și { \ text {else}} \ end {cases}}

Putem apoi defini ierarhia lui Grzegorczyk. , clasa a- n -a (sau nivelul) ierarhiei Grzegorczyk este cel mai mic set care conține ${\ mathcal {E}} ^ {n}$

$E_k$ pentru , $k <n$
funcția nulă,
funcția succesor ( ), $S (x) = x + 1$
proiecții ( ), $p_ {i} ^ {m} (t_ {1}, t_ {2}, \ ldots, t_ {m}) = t_ {i}$

și stabil de

compoziție pe bază ( în cazul în care , , , ..., sunt functii , atunci asa este) $f$ $g_ {1}$ $g_2$ $g_ {m}$ ${\ mathcal {E}} ^ {n}$ $f ({\ bar {u}}) = h (g_ {1} ({\ bar {u}}), g_ {2} ({\ bar {u}}), \ dots, g_ {m} ({ \ bar {u}})))$
recursivitate mărginită, (dacă , și sunt funcții ale și care este astfel încât , și , atunci este, de asemenea, o funcție a ). $g$ $h$ $j$ ${\ mathcal {E}} ^ {n}$ $f$ $\ forall t, \ forall {\ bar {u}}, f (t, {\ bar {u}}) \ leqslant j (t, {\ bar {u}})$ $f (0, {\ bar {u}}) = g ({\ bar {u}})$ $f (t + 1, {\ bar {u}}) = h (t, {\ bar {u}}, f (t, {\ bar {u}}))$ $f$ ${\ mathcal {E}} ^ {n}$

Proprietăți

Avem

{\ mathcal {E}} ^ {0} \ subseteq {\ mathcal {E}} ^ {1} \ subseteq {\ mathcal {E}} ^ {2} \ subseteq \ cdots

de când . $\ {E_ {k} \ mid k <0 \} \ subseteq \ {E_ {k} \ mid k <1 \} \ subseteq \ {E_ {k} \ mid k <2 \} \ subseteq \ cdots$

De fapt, includerea este strictă (Rose 1984; Gakwaya 1997)

{\ mathcal {E}} ^ {0} \ subsetneq {\ mathcal {E}} ^ {1} \ subsetneq {\ mathcal {E}} ^ {2} \ subsetneq \ cdots

deoarece hiperoperarea aparține, dar nu . $H_n$ ${\ mathcal {E}} ^ {n}$ ${\ mathcal {E}} ^ {{n-1}}$

${\ mathcal {E}} ^ {0}$ conține funcții cum ar fi , , , $x \ mapsto x$ $x \ mapsto x + 1$ $x \ mapsto x + 2$
${\ mathcal {E}} ^ {1}$ conține toate funcțiile precum plus , , $x \ mapsto 4x$ $(x, y) \ mapsto x + y$
${\ mathcal {E}} ^ {2}$ conține funcțiile de multiplicare, cum ar fi , , $(x, y) \ mapsto xy$ $x \ mapsto x ^ {4}$
${\ mathcal {E}} ^ {3}$ conține exponentiation funcții, cum ar fi , . Acest set este egal cu cel al funcțiilor elementare , $(x, y) \ mapsto x ^ {y}$ $x \ mapsto 2 ^ {{2 ^ {{2 ^ {x}}}}}$
${\ mathcal {E}} ^ {4}$ conține tetrare .

Relația cu funcțiile primitive recursive

Definiția lui este aceeași cu cea a funcțiilor recursive primitive , cu excepția faptului că construcția recursivă este mărginită ( pentru o anumită funcție ) și funcțiile sunt clar incluse în . Prin urmare, ierarhia Grzegorczyk poate fi văzută ca o modalitate de a limita puterea recursivității primitive. ${\ mathcal {E}} ^ {n}$ $relatii cu publicul$ $f (t, {\ bar {u}}) \ leq j (t, {\ bar {u}})$ $j \ in {\ mathcal {E}} ^ {n}$ $(E_ {k}) _ {{k <n}}$ ${\ mathcal {E}} ^ {n}$

Este clar că funcțiile fiecărui nivel sunt primitive recursive (adică ) și, prin urmare ${\ displaystyle {\ mathcal {E}} ^ {n} \ subseteq PR}$

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

De asemenea, putem arăta că orice funcție primitivă recursivă este prezentă în ierarhia lui Grzegorczyk (Rose 1984; Gakwaya 1997) fie

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

iar mulțimile formează o partiție a setului de funcții primitive recursive . ${\ 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$ $relatii cu publicul$

Extensii

Ierarhia Grzegorczyk poate fi extinsă la ordinali transfiniti . Apoi definim ierarhia creșterii rapide . Pentru aceasta, definiția lui trebuie extinsă pentru ordinali limită, într-adevăr sunt deja definiți pentru ordinali succesori de . Dacă există o metodă standard de definire a unei secvențe fundamentală a cărei limită ordinal este apoi generarea acestor funcții pot fi definite ca fiind . Cu toate acestea, această definiție depinde de secvența fundamentală. Rose (1984) propune o metodă standard pentru orice ordinal . $E _ {\ alpha}$ $E _ {{\ alpha +1}} (n) = E _ {\ alpha} ^ {n} (2)$ $\ lambda _ {m}$ $\ lambda$ $E _ {\ lambda} (n) = E _ {{\ lambda _ {n}}} (n)$ $\ alpha <\ varepsilon _ {0}$

Extensia originală se datorează lui Martin Löb și Stan S. Wainer (1970) și este uneori denumită ierarhia Löb - Wainer.

Bibliografie

Brainerd, WS, Landweber, LH (1974), Theory of Computation , Wiley, ( ISBN 0-471-09585-0 )
Gakwaya, J.–S. (1997), Un sondaj asupra ierarhiei Grzegorczyk și extinderea acesteia prin modelul de calcul al BSS
Grzegorczyk, A. (1953), Unele clase de funcții recursive , Rozprawy matematyczne, Vol 4, p. 1–45 .
Löb, MH și Wainer, SS, „Ierarhii ale funcțiilor teoretice ale numerelor I, II: O corecție”, Arh. Matematica. Logik Grundlagenforschung 14, 1970 p. 198-199 .
Rose, HE, „Subrecursiune: funcții și ierarhii”, Oxford University Press, New York, SUA, 1984. ( ISBN 0-19-853189-3 )
Wagner, K. și Wechsung, G. (1986), Computational Complexity , Mathematics and its Applications v. 21. ( ISBN 978-90-277-2146-4 )