Jerarquia de Grzegorczyk

En teoria de la complexitat, la Jerarquia de Grzegorczyk és una jerarquia de funcions. Cada funció en aquesta jerarquia és una funció recursiva primitiva i tota funció recursiva primitiva apareix a algun nivell d'aquesta aquesta jerarquia. La jerarquia classifica segons el ritme amb què creix cada funció, intuïtivament, les funcions dels nivells més baixos creixen més lentament que les funcions dels nivells més alts.^[1][2]

Definició

Primer es defineixen un conjunt infinit de funcions, amb la lletra ${\displaystyle E_{i}}$ per algun nombre natural i. Es defineix ${\displaystyle E_{0}(x,y)=x+y}$ i ${\displaystyle E_{1}(x,y)=x^{2}+2}$ (${\displaystyle E_{0}}$ és la funció suma i ${\displaystyle E_{1}}$ és la funció unària que eleva al quadrat l'argument i li suma 2). Llavors, per cada n més gran d'1, es defineix ${\displaystyle E_{n}(x)=E_{n-1}^{x}(2)}$ (això és), la x-iteració de ${\displaystyle E_{n-1}}$ avaluada pel 2.^[3]

A partir d'aquestes funcions es defineix la jerarquia de Grzegorczyk ${\displaystyle {\mathcal {E}}^{n}}$, el n-conjunt de la jerarquia, conté les següents funcions:

1. ${\displaystyle E_{k}}$ per ${\displaystyle k<n}$
2. La funció zero ${\displaystyle Z(x)=0}$
3. La funció successor ${\displaystyle S(x)=x+1}$
4. La funció projecció ${\displaystyle p_{i}^{m}(t_{1},t_{2},...,t_{m})=t_{i}}$
5. La composició de funcions generalitzada al conjunt: si ${\displaystyle h,g_{1},g_{2}...,g_{m}}$ son a dins de ${\displaystyle {\mathcal {E}}^{n}}$, llavors ${\displaystyle f({\bar {u}})=h(g_{1}({\bar {u}}),g_{2}({\bar {u}}),...,g_{m}({\bar {u}}))}$ també en pertany.
6. El resultat de la recursió limitada (primitiva) aplicada a funcions dins el conjunt: Si ${\displaystyle g,h{\text{ i }}j}$ son a dins de ${\displaystyle {\mathcal {E}}^{n}}$ i ${\displaystyle f(t,{\bar {u}})\leq j(t,{\bar {u}})}$ per tot ${\displaystyle t{\text{ i }}{\bar {u}}}$, i també ${\displaystyle f(0,{\bar {u}})=g({\bar {u}})}$ i ${\displaystyle f(t+1,{\bar {u}})=h(t,{\bar {u}},f(t,{\bar {u}}))}$, llavors f és a ${\displaystyle {\mathcal {E}}^{n}}$.

En d'altres paraules, ${\displaystyle {\mathcal {E}}^{n}}$ és la clausura del conjunt ${\displaystyle B_{n}={Z,S,(p_{i}^{m})_{i\leq m},E_{k}:k<n}}$ respecte la funció composició i la recursivitat limitada.

Propietats

Aquests conjunts formen clarament la jerarquia

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

ja que son clausures sobre ${\displaystyle B_{n}}$ i ${\displaystyle B_{0}\subseteq B_{1}\subseteq B_{2}\subseteq \cdots }$ Son subconjunts estrictes^[4]:

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

ja que l'hiperoperador ${\displaystyle H_{n}}$ és a ${\displaystyle {\mathcal {E}}^{n}}$ però no a ${\displaystyle {\mathcal {E}}^{n-1}}$.

${\displaystyle {\mathcal {E}}^{0}}$ inclou funcions com x+1, x+2, ...

${\displaystyle {\mathcal {E}}^{1}}$ inclou totes les funcions de suma com x+y, 4x, etc.

${\displaystyle {\mathcal {E}}^{2}}$ inclou totes les funcions de multiplicació com xy, ${\displaystyle x^{4}}$

${\displaystyle {\mathcal {E}}^{3}}$ inclou totes les funcions exponencials, com ${\displaystyle x^{y}}$ o ${\displaystyle 2^{2^{2^{x}}}}$ i és exactament el conjunt de funcions recursives primitives.

${\displaystyle {\mathcal {E}}^{4}}$ inclou totes les funcions tetració, etc.

Cal fer notar que la funció ${\displaystyle U}$ i la funció característica del predicat ${\displaystyle T}$ de la forma normal del teorema de Kleene es pot definir de manera que romanen al nivell ${\displaystyle {\mathcal {E}}^{0}}$ de la jerarquia. Això implica que tot conjunt recursivament enumerable és enumerable per una funció ${\displaystyle {\mathcal {E}}^{0}}$

Relació amb les funcions recursives primitives

La definició de ${\displaystyle {\mathcal {E}}^{n}}$ és la mateixa que la de les funcions recursives primitives, PR, excepte en que la recursió està limitada (${\displaystyle F(t,{\bar {u}})\leq j(t,{\bar {u}})}$ per algun ${\displaystyle j}$ a ${\displaystyle {\mathcal {E}}^{n}}$) i les funcions ${\displaystyle (E_{k})_{k<n}}$ estan explícitament incloses a ${\displaystyle {\mathcal {E}}^{n}}$. Per tant, la jerarquia de Grzegorczyk pot ser vista com una manera de limitar la potència de les funcions recursives primitives a diferents nivells.

A partir d'aquest fet és clar que totes les funcions en un nivell de la jerarquia son funcions recursives primitives (${\displaystyle {\mathcal {E}}^{n}\subseteq {\mathsf {PR}}}$) i per tant:

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

També es pot veure que totes les funcions recursives primitives estan a algun nivell de la jerarquia:

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

I els conjunts ${\displaystyle {\mathcal {E}}^{0},{\mathcal {E}}^{1}-{\mathcal {E}}^{0},{\mathcal {E}}^{2}-{\mathcal {E}}^{1},\dots ,{\mathcal {E}}^{n}-{\mathcal {E}}^{n-1},\dots }$ particionen el conjunt de funcions recursives primitives ${\displaystyle {\mathsf {PR}}}$.

Referències

Vegeu també

• ELEMENTARY