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 como argumentos y devuelve un único número natural. Como norma general se define como sigue:



  A(m,n)=
    \begin{cases}
     n+1,               &\mbox{si }m=0;
    \\
     A(m-1, 1),         &\mbox{si }m>0\mbox{ y }n=0;
    \\
     A(m-1, A(m, n-1)), &\mbox{si }m>0\mbox{ y }n>0
    \end{cases}


Ahora bien, a efectos pedagógicos se puede utilizar una versión alternativa:


 f_{0}(x) = s(x) \,
f_{1}(x) = f_{0}^{x+2}(x) = s^{x+2}(x)
f_{2}(x) = f_{1}^{x+2}(x) = (s^{x+2})^{x+2}(x)
f_{k+1}(x) = f_{k}^{x+2}(x)


Donde s(x) es la función sucesor y fn(x) es la función potencia (aquella que aplica f n veces).

Contenido

Propiedades

  • Sea k \in \mathbb{N} ,\; f_{k} \in FRP
  • Sea \; a > b ,\; f_{k}(a) > f_{k}(b)
  • Sea \; x,k \in \mathbb{N} ,\; f_{k}(x) > x
  • Sea \; k \in \mathbb{N} ,\; f_{k+1}(x) > f_{k}(x)

Además la función de Ackerman (ACK(x) = fx(x)) no es FRP (función recursiva primitiva). La demostración de este teorema se lleva a cabo por reducción al absurdo y utilizando el lema de que toda función recursiva primitiva está mayorada por una función Ackermann.


Comenzamos suponiendo que  ACK(x) \in FRP , por tanto   ACK(x)+1 \in FRP


Usando el lema de la mayoración, debe existir un k tal que  ACK(x)+1 \le f_{k}(x)


Pero entonces, como esto vale para todo x, también valdrá para x=k

ACK(k)+1 \le f_{k}(k) , usando la definición, llegamos a que:


ACK(k)+1 \le ACK(k)


Lo cual es absurdo.

Esta función crece extremadamente rápido: el valor A(4,2) ya tiene 19.729 dígitos. Este crecimiento desmesurado se puede utilizar para demostrar que la función computable f(n) = A(n, n) crece más rápido que cualquier función recursiva primitiva, y por ello no es recursiva primitiva.

Tabla de valores

Números de A(m,n)
m\n 0 1 2 3 4 n
0 1 2 3 4 5 n + 1
1 2 3 4 5 6 n + 2
2 3 5 7 9 11 2n + 3
3 5 13 29 61 125 8\cdot 2^n-3
4 13 65533 2^{65536}-3 \approx 2 \cdot 10^{19728}  A(3,265536-3) A(3,A(4,3)) 2^{2^{\dots^2}}-3 (n + 3 términos)
5 65533 A(4,65533) A(4,A(5,1)) A(4,A(5,2)) A(4,A(5,3))
6 A(5,1) A(5,A(5,1)) A(5,A(6,1)) A(5,A(6,2)) A(5,A(6,3))

Para darse una idea de la magnitud de los valores que aparecen de la fila 4 en adelante, se puede destacar que por ejemplo, A(4, 2) es mayor que el número de partículas que forman el universo elevado a la potencia 200 y el resultado de A(5, 2) no se puede escribir dado que no cabría en el Universo físico. En general, por debajo de la fila 4, ya no es posible escribir todos los dígitos del resultado de la función.

Explicación intuitiva

La primera fila de la función de Ackerman contiene los enteros positivos, dado que A(0, n)) consiste en sumar uno a n. El resto de las filas se pueden ver como indirecciones hacia la primera. En el caso de m = 1, se redirecciona hacia A(0, n + 1), sin embargo, la simplificación es algo complicada:

A \,(1, 2)
 
 
 
 
= A \,(0, A(1,1))
= A \,(0, A(0, A(1,0)))
= A \,(0, A(0, 2))
= A \,(0, 3)
= 4 \,


Se puede intentar con un caso algo más complicado— como A(4, 3); el primer valor que no cabe en el universo físico.

A \,(4, 3)
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
= A \, (3, A(4, 2))
= A \, (3, A(3, A(4, 1)))
= A \, (3, A(3, A(3, A(4, 0))))
= A \, (3, A(3, A(3, A(3, 1))))
= A \, (3, A(3, A(3, A(2, A(3, 0)))))
= A \, (3, A(3, A(3, A(2, A(2, 1)))))
= A \, (3, A(3, A(3, A(2, A(1, A(2, 0))))))
= A \, (3, A(3, A(3, A(2, A(1, A(1, 1))))))
= A \, (3, A(3, A(3, A(2, A(1, A(0, A(1, 0)))))))
= A \, (3, A(3, A(3, A(2, A(1, A(0, A(0, 1)))))))
= A \, (3, A(3, A(3, A(2, A(1, A(0, 2))))))
= A \, (3, A(3, A(3, A(2, A(1, 3)))))
= A \, (3, A(3, A(3, A(2, A(0, A(1, 2))))))
= A \, (3, A(3, A(3, A(2, A(0, A(0, A(1, 1)))))))
= A \, (3, A(3, A(3, A(2, A(0, A(0, A(0, A(1, 0))))))))
= A \, (3, A(3, A(3, A(2, A(0, A(0, A(0, A(0, 1))))))))
= A \, (3, A(3, A(3, A(2, A(0, A(0, A(0, 2))))))
= A \, (3, A(3, A(3, A(2, A(0, A(0, 3)))))
= A \, (3, A(3, A(3, A(2, A(0, 4)))))
= A \, (3, A(3, A(3, A(2, 5))))


Para seguir calculando este valor, habría que encontrar que A(2, 5) vale 13, luego evaluar A(3, 13), que es 8179. Sin embargo, el valor de A(3, 8179) es comparable al número de átomos del Universo elevado a una potencia de más de 12. Ese número tendría que calcularse para hacer la llamada más externa a la función, pero ya no sería posible escribir los dígitos del resultado en el universo físico.

Todo esto por composición de la única operación aritmética que se utiliza, es decir, el incremento en uno de un valor (en el cálculo de A(0, n)).

Descripción explícita

Intuitivamente, la función de Ackermann define la generalización de la multiplicación por dos (sumas iteradas) y la exponenciación con base 2 (productos iterados) hasta la exponenciación iterada; la iteración de la exponenciación iterada; la iteración de la operación anterior;... etc. Puede expresarse de forma concisa y no recursiva mediante la notación de flecha de Conway:

A(m,n)=2\rightarrow (n+3)\rightarrow (m-2)-3

o los hiper operadores:

A(m,n)=\mathrm{hyper}(2,n+3,m-2)-3 \;

Historia

En 1928, Wilhelm Ackermann consideró una función doblemente recursiva A(mnp) de tres variables: m → n → p en la notación de Conway. Ackermann demostró que se trata de una función recursiva que no es primitiva recursiva. Esa definición fue simplificada por Rózsa Péter y Raphael Robinson a la versión de dos variables. Rozsa Peter también demostró que la doble recursión no se puede reducir a recursión primitiva (y que de igual forma la triple recursión no se puede reducir a recursión primitiva y doble recursión, etc).

Sin embargo, la primera función doblemente recursiva que no es recursiva primitiva fue descubierta por Gabriel Sudan en 1927:

F _0 (x, y) = x+y,\,
F _{n+1} (x, 0) = x, \  n \ge 0\,
F _{n+1} (x, y+1) = F _n (F_{n+1} (x, y), F_{n+1} (x, y) + y + 1), \ n\ge 0.\,

Tanto Sudan como Ackermann eran alumnos de David Hilbert en ese entonces.

Análisis de algoritmos

Así como la función diagonal  f (n) = A(nn) crece muy rápidamente, su inversa crece muy lentamente y se utiliza frecuentemente en análisis de algoritmos. En ese contexto, se suele redefinir la función de Ackermann por otra de comportamiento asintótico similar, pero evitando los términos −3, o partiendo de la potencias de 2 para la fila 0 (lo que equivale a omitir las tres primeras filas). Si bien el resultado de estas variantes no es idéntico al de la función original, se pueden ver como similares al ser posible acotar la diferencia. En el caso de la inversa de la función diagonal, su resultado es inferior a 4 para entradas de prácticamente cualquier tamaño, de manera que se asimila a una función constante.

Medida de comparación

Debido a su definición, profundamente recursiva, la función de Ackermann se utiliza con frecuencia para comparar compiladores en cuanto a su habilidad para optimizar la recursión. Por ejemplo, un compilador capaz de notar que A(3, 30) se puede calcular basándose en potencias de 2, o que guarda resultados intermediarios tales como A(3, n) y A(2, n) en lugar de recalcularlos cada vez, ahorraría tiempo de ejecución por un factor de 100 o 1000. Igualmente, al calcular directamente A(1, n) en lugar de hacer una llamada recursiva se realizan ahorros significativos.

Es posible calcular el término A(4, 2) pero no recursivamente, sino por otros medios.

Código C


int Ackermann(int n, int m)
{
     if(n==0) return m+1;
     else if(m==0) return Ackermann(n-1,1);
     else return Ackermann(n-1,Ackermann(n,m-1));
}

Código de Haskell

ack 0 n = n + 1
ack m 0 = ack (m - 1) 1
ack m n = ack (m - 1) (ack m (n - 1))
Véase también: Haskell

Código de Prolog

ackermann(0,N,R):- R is N+1.
ackermann(M,0,R):- M1 is M-1,
                   ackermann(M1,1,R).
ackermann(M,N,R):- M1 is M-1,
                   N1 is N-1,
                   ackermann(M,N1,R1),
                   ackermann(M1,R1,R).

Código de Ada

function Ackermann (m, n : Integer) return Integer is
begin
   if m = 0 then
      return n + 1;
   elsif m > 0 and n = 0 then
      return Ackermann (m - 1, 1);
   elsif m > 0 and n > 0 then
      return Ackermann (m - 1, Ackermann (m, n - 1));
   end if;
end Ackermann;

Código Pascal

program ackermann;{compatible hasta el par(4,0)}

uses crt;
procedure leerpar(var m,n:integer);
begin
writeln('ingrese el un numero');
readln(m);
writeln('ingrese el otro numero');
readln(n);
end;
function ackermann(m,n:integer):longint;
begin
if m=0 then
 ackermann:=n+1
else
 if (m > 0) and (n=0) then
   ackermann:= ackermann(m-1,1)
 else
   if (m > 0) and (n >0)then
     ackermann:= ackermann((m-1), ackermann(m,n-1));
end;
var
m,n:integer;
begin
clrscr;
leerpar(m,n);
writeln(ackermann(m,n));
readkey;
end.

Código de Python

def Ackermann(n, m):
        if n==0:
                return m+1
        elif m==0:
                return Ackermann(n-1,1)
        else:
                return Ackermann(n-1,Ackermann(n,m-1))
Véase también: Python

Véase también

Bibliografía

  • Ackermann, Wilhelm: Zum Hilbertschen Aufbau der reelen Zahlen. Math. Annalen 99 (1928), pp. 118-133.
  • von Heijenoort, J. (ed.): From Frege to Gödel: A Source Book in Mathematical Logic. Cambridge: Harvard University Press, 1967. Disponible en línea.
  • Kozen, Dexter C.: The Design and Analysis of Algorithms. Springer, 1992.
  • Robinson, Raphael M.: Recursion and double recursion. Bull. Amer. Math. Soc., Vol. 54, pp. 987-993.
  • Schöning, Uwe: Theoretische Informatik – kurzgefasst. Spektrum Akademischer. ISBN 3-8274-1099-1
  • Sundblad, Yngve: The Ackermann Function. A Theoretical, Computational, and Formula Manipulative Study. BIT 11 (1971), 107-119.

Enlaces externos


Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Función de Ackermann — La función de Ackermann, utilizada en la teoría de la computación, es una función recursiva que toma dos números naturales como argumentos y devuelve un número natural …   Enciclopedia Universal

  • Ackermann — puede hacer referencia a las siguientes personas: Wilhelm Ackermann Función de Ackermann Rosemarie Ackermann Lutz Ackermann Franz Ackermann Max Ackermann Christian Ackermann Lea Ackermann Geometria de Ackermann Louise Victorine Ackermann Konrad… …   Wikipedia Español

  • Función recursiva — En lógica matemática y computación, las funciones recursivas o también conocidas como funciones recursivas μ son una clase de funciones de los números naturales en los números naturales que son «computables» en un sentido intuitivo. De hecho, en… …   Wikipedia Español

  • Función recursiva — En lógica matemática y computación, las funciones recursivas o también conocidas como funciones recursivas µ son una clase de funciones de los números naturales en los números naturales que son «computables» en un sentido intuitivo. De hecho, en… …   Enciclopedia Universal

  • Wilhelm Ackermann — (29 de marzo 1896 24 de diciembre 1962) fue un matemático alemán. Es conocido, sobre todo, por la función de Ackermann nombrada en su honor, un ejemplo importante en la teoría de la computación. Ackermann nació el 29 de ma …   Wikipedia Español

  • Wilhelm Ackermann — (29 de marzo 1896 24 de diciembre 1962) fue un matemático alemán. Es conocido, sobre todo, por la función de Ackermann nombrada en su honor, un ejemplo importante en la teoría de la computación. Ackermann nació el 29 de marzo de 1896 en… …   Enciclopedia Universal

  • Lisp — Información general Paradigma multiparadigma: orientado a objetos, funcional, declarativo Apareció en 1958 Diseñado por John McCarthy …   Wikipedia Español

  • Mayoración — Una función f (de orden 1) mayora a una g (de orden n) si y sólo si: Notación: Contenido 1 Teoremas referidos a la mayoración 1.1 Lemas …   Wikipedia Español

  • Anexo:Funciones matemáticas — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español

  • Recursión primitiva — Saltar a navegación, búsqueda En Teoría de la computabilidad, la recursión primitiva permite definir una clase de funciones que forman un importante paso en la formalización de la noción de computabilidad. Se definen usando como principales… …   Wikipedia Español


Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.