Siguiente: Propiedades de la escala Un nivel arriba: Jerarquía de Grzegorczyk Anterior: Jerarquía de Grzegorczyk

Una escala de funciones

Consideremos la sucesión $F=\{f_n:I\!\!N^2\rightarrow I\!\!N\}_{n\in I\!\!N}$ definida como sigue:

   

f₀(x,y) = y+1 (1)

f₁(x,y) = x+y (2)

f₂(x,y) = (x+1)(y+1) (3)

y para cada $n\geq 3$ definimos inductivamente

  

f_n(0,y) = f_n-1(y+1,y+1) (4)

$$\forall x>0:\;f_n(x,y)$$ = f_n(x-1,f_n(x-1,y)) (5)

La relación 2.4 indica que, en ``su primer renglón'', la n-ésima función asume los valores en la diagonal de la (n-1)-ésima, corridos una posición hacia adelante. Ahora bien, hablando de manera tosca y ambigua en demasía, podríamos decir que la relación 2.5 indica que, en ``su x-ésimo renglón'', la n-ésima función está ``reiterando x veces los valores previos de esa misma n-ésima función''. La primera función construída según 2.4 y 2.5, a saber, f₃, tiene, en cada renglón, un crecimiento polinomial muy rápido en términos de y, pero, en cada columna, tiene un crecimiento doblemente exponencial en términos de x. En la tabla 2.3 presentamos las formas que asume f₃(x,y) haciendo sustituciones para los primeros valores de x.

  

Table 2.3: Formas de f₃(x,y), con x=0,1,2,3.

De hecho, puede verse que, en general,

$$f_3(x,y) =\underbrace{(2+(2+\ldots(2+}_{2^x\mbox{\rm veces}}y \underbrace{)^2\ldots)^2)^2}_{2^x\mbox{\rm veces}}.$$

así pues f₃(x,y) es un polinomio en y de grado 2^2x. Por tanto, tendremos que $f_4(0,\cdot):y\mapsto \underbrace{(2+(2+\ldots(2+}_{2^{(y+1)}\mbox{\rm veces}}\;(y+1) \underbrace{)^2\ldots)^2)^2}_{2^{(y+1)}\mbox{\rm veces}}.$ Aquí ya es evidente que se carece de notación ``aritmética'' para escribir a $f_4(1,\cdot):y\mapsto f_4(0,f_4(0,y))$, ya sin decir más de $f_4(x,\cdot)$ con $x\geq 2$. $f_5(0,\cdot)$ toma los valores en la diagonal de f₄ y reinicia el proceso. Et cetera. No es presuntuoso afirmar que el crecimiento de f₁₀ o de f₁₉₉₈ o de f_{1998¹⁹⁹⁸} supera, con mucho, los alcances de nuestro propio entendimiento.
Siguiente: Propiedades de la escala Un nivel arriba: Jerarquía de Grzegorczyk Anterior: Jerarquía de Grzegorczyk