La guía o código que hallarás en este post es la solución más fácil y efectiva que encontramos a tus dudas o dilema.
Solución:
La función inversa de Ackermann es recursiva primitiva.
Una forma de ver esto es usar el hecho de que una función $f$ es recursiva primitiva cuando y solo cuando
- la gráfica de $f$ es recursiva primitiva, y
- $f$ está acotado arriba por alguna función recursiva primitiva.
La gráfica de la función de Ackermann es recursiva primitiva, es decir, la función característica del conjunto $lbrace langle x, y, z rangle : z = A(x,y)rbrace$ es recursiva primitiva. Esto se debe a que verificar que $A(x,y) = z$ es fácil una vez que se dan $x, y, z$. Siempre se puede construir una tabla de todos los valores anteriores de $A$ utilizados para justificar que $A(x,y) = z$. Si $z$ es realmente la respuesta correcta, entonces el código de esta tabla no es mucho más grande que $langle x, y, zrangle$ (menor que $17^17^x+y+z$, por ejemplo). Entonces, dado un triple $langle x, y, z rangle$ propuesto, podemos buscar la tabla relevante y determinar si $A(x,y) = z$ es o no true en forma recursiva primitiva. Por supuesto, la función de Ackermann no está limitada arriba por una función recursiva primitiva, pero eso es lo único que falla.
Dado que la gráfica de la función de Ackermann es recursiva primitiva, también lo es la gráfica de la función inversa de Ackermann $Ack^-1(z) = maxlbrace x : A(x,x) leq zrbrace$ . 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 de hecho recursivo primitivo.
Tal vez lo siguiente sea de interés.
Hay un indicador en la literatura proporcionada por el libro de Soare sobre re grados. En un ejercicio se debe mostrar que las funciones recursivas primitivas biyectivas no forman un grupo. En términos generales, la sugerencia sugiere que la inversa de la función de Ackermann no tiene una inversa prim rec.
valoraciones y reseñas
Puedes amparar nuestra faena ejecutando un comentario y dejando una valoración te damos las gracias.