Estoy leyendo "Introducción a la Lógica Matemática, Sexta Edición" (por Elliott Mendelson) y confundidos en la Proposición 3.17 (página 179), que es acerca de recursión primitiva obtenidos a partir delimitada suma. Entiendo que la propuesta, lo cual indica que si $f(x_1,...,x_n, y)$ es primitiva recursiva, entonces el delimitada suma $g(x_1,...,x_n, z) = \sum_{y<z}f(x_1,...,x_n, y)$ también es primitiva recursiva. La prueba es simple y directo.
Ahora mi pregunta es: ¿qué pasa si en el balance el valor de $f$ depende también de $z$? Es decir, es $g(x_1,...,x_n, z) = \sum_{y<z}f(x_1,...,x_n, y, z)$ también primitiva recursiva?
El autor dio un ejemplo (página 179), $\tau(x) = \sum_{y \leq x} \overline{sg}(rm(y, x))$, y afirma que es primitiva recursiva. Parece que se puede demostrar directamente de la Proposición 3.17. Pero no aparece así, como $\overline{sg}(rm(y, x))$ es una función de $f(x, y)$ que depende también de la $x$.
Una manera de resolver este problema parece ser: si en la sumatoria $\sum_{y<z}f(x_1,...,x_n, y, z)$ la función de $f$ es obtenido por la "recursividad en $z$", es decir, $f(x_1,...,x_n, y, z)$ depende de $f(x_1,...,x_n, y, z-1)$ que también depende de la $f(x_1,...,x_n, y, z-2)$ y así sucesivamente, entonces podemos encontrar una función $h(x_1,..., x_n, y) = f(x_1,...,x_n, y, z)$. Esto significa que podemos eliminar la dependencia de $z$ $h$ también es primitiva recursiva.
El método anterior sólo se aplica a determinados casos. Es el caso general, cierto?
