Función de Ackermann y recursividad primitiva

Question

Si definimos $b_n(m) := a(n,m)$ para todos $n$ y $m \in \mathbb{N}$ . Para lo cual $n$ es la función $b_n$ primitiva recursiva y para la cual $n$ ¿no es una función recursiva primitiva? ¿Puede alguien ayudarme con esto?

Answer 1

Supongo que (como sugiere el título) $$ a(n,m) = \begin{cases} m +1 & n= 0\\ a(n-1, 1) & n > 0, m=0\\ a\bigl(n-1, a(n,m-1)\bigr) \end{cases} $$ denota la función de Ackermann. Reescribiendo esto en términos de $b_n$ tenemos $b_0 = \cdot + 1$ es la función sucesora y $$ b_n(m) = \begin{cases} b_{n-1}(1) & m = 0 \\ b_{n-1}\bigl(b_n(m-1)\bigr)\end{cases} $$ Si $b_{n-1}$ es recursivo primitivo, esto define una función recursiva primitiva $b_n$ . Como $\cdot + 1$ es recursivo primitivo, por inducción, todo $b_n$ son.