Siguiente: Función de Ackermann Un nivel arriba: Jerarquía de Grzegorczyk Anterior: Propiedades de la escala

Niveles de la jerarquía

Para cada $n\geq 0$ consideremos la clase de funciones ``generada'' por la función f_n, es decir, para cada $n\geq 0$,

Proposición 3.3   ${\cal E}^3$ coincide con la clase de las funciones elementales, es decir, ${\cal E}= {\cal E}^3.$

En efecto, consideremos las presentaciones de las funciones elementales en la tabla 2.2. Veamos que ${\cal F}^3\subset {\cal E}^3$. Para esto basta definir a la exponenciación en ${\cal E}^3$. Puede verse que para cualesquiera x,y se cumple $x^y\leq f_3(x,y)$. Ahora, es claro que la exponenciación puede definirse por el esquema de recursión utilizando al producto usual, y, de hecho, utilizando a f₃ la recursión puede hacerse de manera acotada. Por tanto, la exponenciación está en ${\cal E}^3$, $\left[(x,y)\mapsto x^y\right]\in {\cal E}^3.$ Para probar la inclusión opuesta basta ver que f₃ se puede definir en ${\cal F}^3$. De las igualdades en 2.7, al considerar el polinomio cuadrático $g:y\mapsto (2+y)^2$ y al hacer

$$\begin{array}{lcl} h(0,y) &=& y \\ h(x+1,y) &=& g(h(x,y)) \end{array}$$

vemos que $h(x,y)\leq (2+y)^{2^{2^x}}$ y, según 2.7, f₃(x,y)=h(2^x,y). De todo esto resulta que f₃ es efectivamente constructible en ${\cal F}^3$.

Proposición 3.4   Las primeras cuatro clases de la escala están anidadas de manera creciente,

$${\cal E}^0\subset {\cal E}^1\subset {\cal E}^2\subset {\cal E}^3.$$

En efecto, cada una de las inclusiones enlistadas se demuestra directamente.

Proposición 3.5   Para todo n: ${\cal E}^n\subset {\cal E}^{n+1}$.

Demostración: Veamos que rige la implicación

$$i\leq n\;\Rightarrow\;f_i\in {\cal E}^n.$$

Vimos que f_i(x,y)=g_i^22x(y). Comprobaremos que la expresión del lado derecho se construye en ${\cal E}^n$. Definamos, como lo hicimos para f₃,

$$\begin{array}{lcl} h_i(0,y) &=& y \\ h_i(x+1,y) &=& g_i(h_i(x,y)) \end{array}$$

entonces $h_i(x,y)\leq g_i^{2^{2^x}}(y)$ y, según la proposición 2.3.1, f_i(x,y)=h(2^x,y). De todo esto resulta que f_i es efectivamente constructible en ${\cal F}^n$, siempre que $i\leq n$.

Proposición 3.6   La clase de funciones recursivas primitivas coincide con la unión de las ${\cal E}^n$'s, es decir

$${\cal FRP}= \bigcup_{n\geq 0}{\cal E}^{n}.$$

Demostración: ${\cal FRP}$ es cerrada bajo los esquemas de formación de cada ${\cal E}^n$. Como también las funciones básicas de ${\cal E}^n$ son recursivas primitivas se tiene $\forall n:{\cal E}^{n}\subset {\cal FRP}$ y consecuentemente $\bigcup_{n\geq 0}{\cal E}^{n}\subset {\cal FRP}.$ Para demostrar la inclusión ${\cal FRP}\subset \bigcup_{n\geq 0}{\cal E}^{n}$, hay que demostrar, y nosotros omitiremos aquí su demostración, el siguiente

Lema 3.1   Si $f\in{\cal FRP}$ requiere de la aplicación de n reglas, sean de composición o de recursión, para ser definida en ${\cal FRP}$, entonces necesariamente $f\in{\cal E}^{n+3}$.

Ahora, puede verse que $\forall n:{\cal E}^{n+1}-{\cal E}^{n}\not=\emptyset$.

Proposición 3.7   La diagonal de f_n+1 crece más rápido que cualquier función en ${\cal E}^n$, es decir

$$\forall f\in {\cal E}^n\exists x_f\in I\!\!N:\; x\geq x_f\;\Rightarrow f_{n+1}(x,x)>f(x).$$

Corolario 3.1   De lo anterior se desprenden los resultados siguientes:

1.

Para todo n: ${\cal E}^n\not= {\cal E}^{n+1}$.

2.

La clase de las funciones elementales es un subconjunto propio de las recursivas primitivas.

3.

El esquema de recursión acotada es insuficiente para definir a las funciones recursivas primitivas.

Siguiente: Función de Ackermann Un nivel arriba: Jerarquía de Grzegorczyk Anterior: Propiedades de la escala