Función de Ackermann

En teoría de la computación,función de Ackermann es una función matemática recursiva encontrada en 1926 por Wilhelm Ackermann, tiene un crecimiento extremadamente rápido, de interés para la ciencia computacional teórica y la teoría de la computabilidad. Hoy en día, hay una serie de funciones que son llamadas funciones Ackermann. Todas ellas tienen una forma similar a la ley original la función de Ackermann y también tienen un comportamiento de crecimiento similar. Esta función toma dos números naturales como argumentos y devuelve un único número natural. Como norma general se define como sigue:

Propiedades

  • Sea
  • Sea
  • Sea
  • Sea

Además la función de Ackerman () 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 , por tanto

Usando el lema de la mayoración, debe existir un k tal que

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

, usando la definición, llegamos a que:

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.

Other Languages