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
- el gráfico de $f$ es recursivo primitivo, y
- $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.
