Por $\uparrow$ Me refiero a la notación de Knuth. En particular, $$x\uparrow\uparrow x=x^{x^{\cdots^{x}}},$$ donde se itera la exponenciación $x$ muchas veces. Sospecho que no, ya que creo que puede crecer más rápido que la función Ackerman, pero no estoy seguro de cómo ver esto.
Respuesta
¿Demasiados anuncios?
Milo Brandt
Puntos
23147
Si $f(a,b)$ es recursivo primitivo, entonces también lo es $$g(n,a,b)=\underbrace{f(a,f(a,\ldots,f(a}_{n\text{ applications of }f(a,-)},b)\ldots))$$ Esto es bastante fácil por definición, ya que $g$ se define por $$g(0,a,b)=b$$ $$g(S(n),a,b)=f(a,g(n,a,b))$$ que tiene la forma adecuada para una recursión primitiva. En particular, se puede obtener la tetración a partir de la exponenciación de la misma manera que se obtendría la exponenciación a partir de la multiplicación o la multiplicación a partir de la suma - esencialmente, sólo se aplica este proceso donde $f(a,b)=a^b$ y al final considerar $g(x,x,x)$ .
El problema con la función Ackermann es que "iterar el proceso de iteración de la última función binaria" no puede expresarse por sí mismo con una función recursiva primitiva, aunque lo haga cualquier número fijo de veces puede .
