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 que creix cada funció, intuïtivament, les funcions dels nivells més baixos creixen més lentament que les funcions dels nivells més alts.

Definició

Primer es defineixen un conjunt infinit de funcions, amb la lletra $E_{i}$ per algun nombre natural i. Es defineix $E_{0}(x,y)=x+y$ i $E_{1}(x,y)=x^{2}+2$ ($E_{0}$ és la funció suma i $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 $E_{n}(x)=E_{n-1}^{x}(2)$ (això és), la x-iteració de $E_{n-1}$ avaluada pel 2.

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

1. $E_{k}$ per $k<n$
2. La funció zero $Z(x)=0$
3. La funció successor $S(x)=x+1$
4. La funció projecció $p_{i}^{m}(t_{1},t_{2},...,t_{m})=t_{i}$
5. La composició de funcions generalitzada al conjunt: si $h,g_{1},g_{2}...,g_{m}$ son a dins de ${\mathcal {E}}^{n}$, llavors $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 $g,h{\text{ i }}j$ son a dins de ${\mathcal {E}}^{n}$ i $f(t,{\bar {u}})\leq j(t,{\bar {u}})$ per tot $t{\text{ i }}{\bar {u}}$, i també $f(0,{\bar {u}})=g({\bar {u}})$ i $f(t+1,{\bar {u}})=h(t,{\bar {u}},f(t,{\bar {u}}))$, llavors f és a ${\mathcal {E}}^{n}$.

En d'altres paraules, ${\mathcal {E}}^{n}$ és la clausura del conjunt $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

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

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

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

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

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

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

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

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

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

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

Relació amb les funcions recursives primitives

La definició de ${\mathcal {E}}^{n}$ és la mateixa que la de les funcions recursives primitives, PR, excepte en que la recursió està limitada ($F(t,{\bar {u}})\leq j(t,{\bar {u}})$ per algun $j$ a ${\mathcal {E}}^{n}$) i les funcions $(E_{k})_{k<n}$ estan explícitament incloses a ${\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 (${\mathcal {E}}^{n}\subseteq {\mathsf {PR}}$) i per tant:

$\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:

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

I els conjunts ${\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 ${\mathsf {PR}}$.

Vegeu també

• ELEMENTARY