Me encontré con esta pregunta porque yo mismo quería demostrar algo muy parecido (mientras enseño un curso sobre computabilidad, ¡así que esto no es tarea para mí!). Desgraciadamente, la pregunta estaba planteada de tal manera que casi nadie parece haber entendido la verdadera cuestión, y en particular no he encontrado ninguna respuesta adecuada ni aquí ni en MathOverflow. Así que voy a tratar de dar lo mejor de mí, pero me gustaría mucho aprender una respuesta más simple (dado que era la tarea, tal vez el OP aprendido una solución por ahora?).
Así que, en primer lugar, la dificultad es que mientras el esquema básico de la recursión primitiva permite pasar parámetros adicionales que no son objeto de la recursión ( $\bar x$ en el texto de la pregunta) sin cambios, la pregunta se refiere a qué hacer cuando este parámetro se modifica por la aplicación de $\pi$ . Que esto no es en general inocente puede demostrarse mediante la función de Ackermann, que opera mediante una modificación similar de su parámetro de no recursión, y que es no primitivo recursivo (por supuesto la modificación es aquí en términos de la propia función de Ackermann mientras que en la pregunta $\pi$ debe ser recursivo primitivo, por lo que aún podemos esperar una respuesta positiva).
Primero asumiré que $\pi$ satisface $\pi(x,y)\leq y$ para todos $x,y$ para que las relaciones de recursión sólo disminuyan el parámetro adicional $y$ . En ese caso se tiene la siguiente solución, algo similar a cómo Recurrencia de curso de valores se maneja: definir primero otra función $H$ de dos argumentos por $H(x,y)=\left<h(x,0),\ldots,h(x,y)\right>$ la codificación de la lista indicada en un solo número; aunque aparentemente $H$ es más complicado que $h$ puede definirse más directamente mediante una recursión primitiva. En efecto, lo que se necesita es una función recursiva primitiva $G$ para calcular $H(x+1,y)=\left<h(x+1,0),\ldots,h(x+1,y)\right>$ dados los valores $x$ , $y$ y $H(x,y)=\left<h(x,0),\ldots,h(x,y)\right>$ . Debería devolver una lista con el componente final $h(x+1,y)=g(x,y,h(x,\pi(x,y)))$ donde $h(x,\pi(x,y))$ es uno de los componentes de $H(x,y)$ por la suposición $\pi(x,y)\leq y$ . Este componente puede calcularse a partir de $x,y,H(x,y)$ mediante una función recursiva primitiva, por ejemplo $G_0(x,y,z)$ con $z$ que se toma como $H(x,y)$ . Ya que lo único que $G_0$ necesita hacer con la lista $z$ es seleccionar un componente del mismo, podemos suponer que devuelve el mismo valor siempre que $z$ se sustituye por una lista más larga que contiene $z$ como prefijo. Ahora podemos definir $G$ primitiva recursivamente por $$ \begin{align*} G(x,0,z) &= \left< G_0(x,0,z) \right> \\ G(x,y+1,z) &= \mathit{append}(G(x,y,z),G_0(x,y+1,z)) \end{align*} $$ donde $\mathit{append}$ añade un elemento a la lista codificada como su primer argumento. (Obsérvese cómo hemos evitado tener que modificar $z$ en la recurrencia para $G$ ya que esto nos habría metido en una situación de huevo y gallina). Ahora podemos definir $H(x,y)$ mediante una recursión primitiva en $x$ utilizando $G$ (Dejo la computación $H(0,y)$ como ejercicio), y finalmente $h(x,y)$ tomando el último elemento de la lista codificada por $H(x,y)$ .
(Otra aproximación más bruta a este caso es definir $h'(z)$ por $h'(\langle x,y\rangle)=h(x,y)$ para una codificación $\langle x,y\rangle$ de la pareja $(x,y)$ cuya codificación puede considerarse biyectiva (cada $z$ codifica un par) y monótona (creciente $x$ o $y$ siempre aumenta el código $\langle x,y\rangle$ (esto es cierto para cualquier codificación razonable). Entonces, como $\langle x+1,y\rangle > \langle x, \pi(x,y)\rangle$ la relación de recurrencia que $h$ debe satisfacer conduce a una recursión de valores para $h'$ que sabemos manejar).
Ahora la mayoría de las funciones recursivas primitivas $\pi$ de dos argumentos hacen por supuesto no satisfacer $\pi(x,y)\leq y$ para todos $x,y$ y si no los métodos anteriores no funcionan. Sin embargo, el aumento del argumento no recursivo no constituye un verdadero obstáculo para el cálculo de $h$ ya que para cada par $(x+1,y)$ podemos predecir (usando $\pi$ ) cuántos valores $(x,y')$ necesitamos calcular $f$ para la primera, y así sucesivamente para la disminución $x$ . Así que intuitivamente podemos calcular $h(x,y)$ calculando "filas" sucesivas (es decir, con $x$ ) hasta un punto computable de antemano. (Esto es distinto a lo que ocurre con la función de Ackermann, en la que cada fila debe desarrollarse sólo hasta un punto finito, pero no predecible hasta que se conozca la propia función de Ackermann).
Para tratar el caso general, primero reduzco al caso que realmente $\pi(x,y)\geq y$ para todos $x,y$ y también que $\pi(x,y)$ es monótona en $y$ al mismo tiempo que se generaliza al caso de que $g$ depende (además de $x$ y $y$ ) no sólo en el valor $h(x,\pi(x,y))$ pero en toda la fila (codificada) $\left<h(x,0),\ldots,h(x,\pi(x,y))\right>$ Como hemos visto, esta generalización no complica esencialmente las cosas. Para obtener la reducción, sustituir $\pi$ por $\pi'$ definido como $\pi'(x,y)=\mathrm{max}(y,\pi(x,0),\ldots,\pi(x,y))$ si es necesario. Ahora bien, la característica que permite predecir cuántos valores hay que precalcular, es que para un determinado $x,y$ el valor final $l(x,y)$ de la secuencia $y$ , $\pi(x-1,y)$ , $\pi(x-2,\pi(x-1,y))$ , ... $\pi(0,\pi(1,\ldots\pi(x-1,y)\ldots))=l(x,y)$ del máximo $y$ -necesarios, respectivamente, para $x$ , $x-1$ , $x-2$ , ..., $0$ puede calcularse de forma primitiva-recursiva. En efecto, este valor viene dado por $l(x,y)=L(x,x,y)$ donde $L$ satisface $$ \begin{align*} L(0,x,y) &= y, \\ L(i+1,x,y) &= \pi(x-i,L(i,x,y)). \end{align*} $$ Obsérvese que por nuestra suposición sobre $\pi$ la función $l$ también es monótona en $y$ y satisface $l(x,y)\geq y$ para todos $x,y$ . Además $l(x+1,y)=l(x,\pi(x,y))$ por definición de $l$ .
Ahora mi idea es definir una función diferente $H(x,z)$ para ayudar a definir $h$ y que codifica la lista de valores $h(x,y)$ para todos $y$ con $l(x,y)\leq z$ . La función $h$ puede definirse entonces tomando $h(x,y)$ sea el valor de la lista $H(x,l(x,y))$ en el índice $y$ que está garantizada su existencia (y probablemente el último valor de la lista). El punto de $H$ es que, por lo que sabemos sobre $l$ la lista codificada por $H(x,z)$ es finito, y $H(x,z)$ contiene todos los valores anteriores $h(x,y)$ que uno necesita saber para calcular los valores (en general mucho menos) codificados en la lista $H(x+1,z)$ . Así que debería ser posible definir $H$ mediante una recursión primitiva en $x$ con $z$ como un segundo argumento invariable. Sin embargo, estoy un poco cansado de dar detalles (y estoy seguro de que el lector también), así que me detendré aquí.
