¿Nada útil proviene de Ackermann ' s función?

Question

Esta es la función:

if (m == 0)
    return n + 1;
else if (n == 0)
    return A(m-1, 1);
else
    return A(m-1, A(m, n-1));

Esto parece una interesante función, especialmente desde que sus valores crecen muy rápidamente (en mi ordenador se bloquea si intento ejecutar Un(4,2) o Un(3,10)).

Desde la página de la wikipedia, parece que sólo se inventó para mostrar que un total computable función no tiene que ser primitiva recursiva. Tiene algo práctico provienen de esta función, aparte de los problemas de la tarea en una clase de informática?

Answer 1

La inversa de la función de Ackermann es útil en la complejidad computacional, por ejemplo, en la línea de los acuerdos y otros problemas en geometría computacional. La aparición en el análisis de algunos de los problemas concretos y los algoritmos es algo sorprendente. Ver

• Davenport–Schinzel secuencias y su papel en la inferior de los sobres
• Davenport-Schinzel Secuencias y Sus Aplicaciones Geométricas

Answer 2

Usamos la inversa de la función de Ackermann en el capítulo 5 de nuestro libro "Untangling gráficos planares de una posición del vértice especificado - casos difíciles" dedicado a los dibujos de línea recta de gráficos planares.