Función de Ackermann

En su versión moderna estándar, esta función toma dos números naturales como argumentos y devuelve un único número natural, y se puede definir de la siguiente manera: Además la función de Ackerman (

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

Esta función crece extremadamente rápido: el valor A(4,2) ya tiene 19.729 dígitos.

En el caso de m = 1, se redirige hacia A(0, n + 1); sin embargo, la simplificación es algo complicada: 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.

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.

Esa definición fue simplificada por Rózsa Péter y Raphael Robinson a la versión de dos variables.

Sin embargo, la primera función doblemente recursiva que no es recursiva primitiva fue descubierta por Gabriel Sudan en 1927: Tanto Sudan como Ackermann eran alumnos de David Hilbert en ese entonces.

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.

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.

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.