Siguiente: Segunda lista de ejercicios Un nivel arriba: Funciones recursivas primitivas Anterior: Niveles de la jerarquía

  
Función de Ackermann

En la sección anterior presentamos una jerarquía para las funciones recursivas primitivas. Se vió que las funciones en un nivel de la jerarquía, que no se encuentran en el nivel anterior, tienen un crecimiento sustancialmente mayor que las funciones en el nivel anterior. Extrapolaremos la construcción presentada para obtener una función con un crecimiento mayor que cualquier función en cualquier nivel de la jerarquía. Tal función no podrá ser recursiva primitiva, pero sí ha de ser computable. Veamos pues la construcción de esa función. La función sucesor $g_0=\mbox{\rm suc}:x\mapsto x+1$ es muy sencilla, desde el punto de vista computacional. La función suma es una reiteración de la sucesor:

$$g_1=\mbox{\rm suc}:(x,y)\mapsto g_0^y(x).$$

La función producto es una reiteración de la suma:

$$g_2=\mbox{\rm pro}:(x,y)\mapsto g_1^{(y)}(x),$$

donde

$$\begin{eqnarray*}g_1^{(1)}(x)&=&x \\ g_1^{(y+1)}(x)&=&g_1(x,g_1^{(y)}(x)) \end{eqnarray*}$$

La función exponencial es una reiteración del producto:

$$g_3=\mbox{\rm exp}:(x,y)\mapsto g_2^{(y)}(x).$$

Continuando con estas reiteraciones podemos considerar

$$g_{n+1}:(x,y)\mapsto g_n^{(y)}(x).$$

Esta es la motivación de la función de Ackermann. Sea $A:I\!\!N^2\rightarrow I\!\!N$ definida como sigue:

$$A(n,m)=\left\{\begin{array}{ll} m+1 &\mbox{\rm si $n=0$}, \\... ...m-1)) &\mbox{\rm si $n\not=0$ y $m\not=0$}. \end{array}\right.$$

Para ilustrar el comportamiento de A, si escribimos h_n(m)=A(n,m) entonces tendremos

$$h_{n+1}(m)=h_n^{m+1}(1),\;\;\forall m>0$$

de lo cual resulta

$$\begin{eqnarray*}h_0(m)&=& m+1 \\ h_1(m)&=& m+2 \\ h_2(m)&=& 2m+3 \\ h_3(m)&=& 2^{m+3}-3 \\ h_4(m)&=& e_{m+3}(2)-3 \end{eqnarray*}$$

donde

$$\begin{array}{lcl} e_1(x)=x & \mbox{\rm y} & e_{y+1}(x)=x^{e_y(x)}.\end{array}$$

Se ve así que esta función crece extremadamente rápido. Una manera de calcular la función de Ackermann es manipulando listas de índices. Utilizaremos ``corchetes'' para denotar aplicaciones sucesivas, siempre por la derecha, de la función de Ackermann. Precisamente,

$$\begin{eqnarray*}{[n_1]} &=& n_1 \\ {[n_1,n_2,\ldots,n_k]} &=& A(n_1,{[n_2,\ldots,n_k]}) \end{eqnarray*}$$

Utilizaremos el símbolo ``$\sim$'' para denotar igualdad de listas bajo esta interpretación. De la definición de la función tenemos

$${[}n,m{]}\sim\left\{\begin{array}{ll} {[}m+1{]} &\mbox{\rm s... ...-1{]} &\mbox{\rm si $n\not=0$ y $m\not=0$}. \end{array}\right.$$

Así pues, dada una lista de enteros $L\in I\!\!N^*$, separemos a sus dos últimos elementos, digamos

L=L'*[n,m]

entonces calculamos la transformación

$$T(L)=\left\{\begin{array}{ll} L'*{[}m+1{]} &\mbox{\rm si $n=... ...box{\rm si $n\not=0$\space y $m\not=0$ }. \end{array}\right.$$ (9)

Tendremos el valor de A(n,m) al obtener, por primera vez, una lista de longitud 1 aplicando sucesivamente la transformación T, a partir de la lista [n,m]. En $I\!\!N^*$ introduzcamos la relación `` $\leq_{\mbox{\rm A}}$'' definiendo

$${\bf m}_1\leq_{\mbox{\rm A}}{\bf m}_2\Leftrightarrow \exists n\geq 0:T^n({\bf m}_2)={\bf m}_1.$$

Resulta evidente que

• $\leq_{\mbox{\rm A}}$ es una relación de orden,
• $\leq_{\mbox{\rm A}}$ es un buen orden, es decir toda cadena posee un mínimo, si y sólo si el procedimiento descrito para calcular la función de Ackermann termina.

Un momento de reflexión basta para convencerse de que $\leq_{\mbox{\rm A}}$ es, en efecto, un buen orden. En la figura 2.1 se muestra un procedimiento alternativo para el cálculo de la función A. El seudocódigo ahí mostrado sigue una sintaxis à la FORTRAN.

  

Figure 2.1: Cálculo de la función de Ackermann.

Proposición 4.1   La función de Ackermann NO es recursiva primitiva.

Justificación: No entraremos en detalles. Tan solo diremos que debido a su definición, puede verse que la función $x\mapsto A(x,x)$ domina, a la larga, a cada una de las funciones $x\mapsto f_n(x,x)$, es decir,

$$\forall n\exists x_n:x\geq x_n \Rightarrow f_n(x,x)<A(x,x)$$ (10)

Si A fuese recursiva primitiva, entonces su diagonal $d_A:x\mapsto A(x,x)$ también sería recursiva primitiva, por lo cual existiría un índice n₀ tal que $d_A\in{\cal E}^{n_0}$. Por la proposición 2.3.7, se tiene $\forall x: d_A(x)<f_{n_0+1}(x,x)$. Esto contradice a la relación 2.10.
Siguiente: Segunda lista de ejercicios Un nivel arriba: Funciones recursivas primitivas Anterior: Niveles de la jerarquía