Ackermann inverso: ¿recursivo primitivo o no?

Question

Quería poner esto originalmente en math.stackexchange, ya que consideré que era una pregunta sencilla y probablemente un hecho bastante conocido. Después de fracasar en la resolución del problema, busqué en la literatura y qué sorpresa: dos libros afirman que es recursiva primitiva, un recurso afirma que no lo es, y ninguno da pruebas o referencias. Un artículo también afirma que la función inversa de Ackermann es más lenta que cualquier función recursiva primitiva. Si fuera recursiva primitiva, no veo por qué habría de ser así.

Ahora, mis preguntas serían: ¿cuál es es la correcta - $Ack^{-1}$ es/no es primitiva recursiva, y es/no es más lenta que cualquier función recursiva primitiva primitiva.

Si es una pregunta mala de MO, la migraré a M.SE, sin problema.

Answer 1

La función inversa de Ackermann es recursiva primitiva.

Una forma de ver esto es utilizar el hecho de que una función $f$ es recursivo primitivo cuando y sólo cuando

1. el gráfico de $f$ es recursivo primitivo, y
2. $f$ está limitada por encima por alguna función recursiva primitiva.

El gráfico de la función de Ackermann es recursivo primitivo, es decir, la función característica del conjunto $\lbrace \langle x, y, z \rangle : z = A(x,y)\rbrace$ es recursivo primitivo. Esto se debe a que la comprobación de que $A(x,y) = z$ es fácil una vez que $x, y, z$ están dadas. Siempre se puede construir una tabla con todos los valores anteriores de $A$ utilizado para justificar que $A(x,y) = z$ . Si $z$ es efectivamente la respuesta correcta, entonces el código de esta tabla no es mucho mayor que $\langle x, y, z\rangle$ (más pequeño que $17^{17^{x+y+z}}$ por ejemplo). Así, dada una propuesta de triple $\langle x, y, z \rangle$ podemos buscar la tabla correspondiente y determinar si $A(x,y) = z$ es verdadera de forma primitiva y recursiva. Por supuesto, la función de Ackermann no está acotada por encima de una función recursiva primitiva, pero eso es lo único que falla.

Como la gráfica de la función de Ackermann es recursiva primitiva, entonces también lo es la gráfica de la función inversa de Ackermann $Ack^{-1}(z) = \max\lbrace x : A(x,x) \leq z\rbrace$ . Además, la tasa de crecimiento de $Ack^{-1}$ está limitada por alguna función recursiva primitiva (por ejemplo, la función de identidad). De ello se deduce que $Ack^{-1}$ es efectivamente recursivo primitivo.

Answer 2

Quizás lo siguiente sea de interés.

Hay un indicador en la literatura que proporciona el libro de Soare sobre los grados r.e. En un ejercicio hay que demostrar que las funciones recursivas primitivas biyectivas no forman un grupo. A grandes rasgos, la pista sugiere que la inversa de la función de Ackermann no tiene prim recursividad.

Answer 3

Una respuesta más intuitiva es que la recursividad primitiva es un tipo de complejidad temporal, se puede calcular una función recursiva primitiva en Ack(k,n) pasos para alguna constante k, y no se puede calcular tan rápido para una función no-pr.

Y para la función inversa de Ackermann, incluso la enumeración por fuerza bruta costará sólo un tiempo exponencial.

Answer 4

En este debate

https://math.stackexchange.com/questions/31294/growth-rate-of-primitive-and-mu-recursive-functions

En el último comentario se dice que el Ackermann inverso NO es recursivo primitivo, pero no tengo ni idea de por qué es así, pero tal vez puedas hacer un seguimiento...

EDITAR Y estos tipos (mucho más confiables), afirman lo contrario:

http://ropas.snu.ac.kr/~gslee/Publi/ackermann_ramsey.pdf