Algoritmo de Ackermann: Funcionamiento y Código en C

Función de Ackermann

En teoría de la computación, la función de Ackermann es una función recursiva que toma dos números naturales y devuelve un único número natural.

En 1928, Wilhelm Ackermann observó que A(x,y,z), la z-ésima exponenciación iterada de x con y como exponente, es una función recursiva que no es recursiva primitiva. En 1935, Rózsa Péter simplificó A(x,y,z) a una función de dos variables. En 1948, Raphael M. Robinson simplificó la condición inicial, quedando una función doblemente recursiva de N² en N, definida recursivamente por las tres condiciones siguientes:

A[0, n_] := n + 1;
A[m_, 0] := A[m - 1, 1];
A[m_, n_] := A[m - 1, A[m, n - 1]];

Esta última versión es conocida hoy día como la función de Ackermann, el ejemplo más simple de una función total que es computable. O sea, que se puede implementar con ciclos de tipo "While". Pero que no es primitiva recursiva. Por tanto no se puede implementar sólo con ciclos de tipo "For".

Esto proporciona un contraejemplo a la creencia de principios del siglo XX de que toda función computable era también recursiva primitiva. Por su definición inicial, la función de Ackermann crece más rápido que cualquier función exponencial, e incluso cualquier función exponencial múltiple.

De hecho, A[4,2] = 2²²²² − 3 = 2⁶⁵⁵³⁶ − 3 es un número natural con más de 19.000 dígitos en base 10.

Aunque correcto y funcional, no permite calcular A[4,2] en un tiempo razonable, en ningún ordenador actual. Sin embargo, el número 2⁶⁵⁵³⁶ − 3 se calcula en segundos.

Lo que enlentece el cálculo de la función de Ackermann, es tener que ir de uno en uno hacia atrás y hacia delante varias veces antes de alcanzar el número final, que acaba siendo enumerado muchas veces.

Código en C

#include <stdio.h>

int ackermann(int,int);

int main(){

int m,n;

printf("Primer argumento para la funcion Ackermann (m): ");

scanf("%d", &m);

printf("Segundo argumento para la funcion Ackermann (n): ");

scanf("%d", &n);

printf("Ackermann (%d,%d) = %d\n", m,n,ackermann(m,n));

return 0;

}

int ackermann(int m, int n){

     if(m==0){

      return n+1;

     }else if(n==0){

      return ackermann(m-1,1);

     }else{

      return ackermann(m-1,ackermann(m,n-1));

     } 

}