In recursion theory, is $\Sigma_{i=0}^y f(x,i,z)$ primitive recursive?

74 Views Asked by At

It is known that given ternary primitive recursive function $f$, the function $g$ defined as

$g(x,y,z)=\Sigma_{i=0}^z f(x,y,i)$ is primitive recursive.

I wonder if this formulation can be modified; i.e., I want to know, given $h_1$ and $h_2$ as $h_1(x,y,z)=\Sigma^y_{i=0}f(x,i,z)$

$h_2(x,y,z)=\Sigma^x_{i=0}f(i,y,z)$,

whether $h_1$ and $h_2$ are primitive recursive.

I tried with primitive recursion formula, but it didn't work to me.

1

There are 1 best solutions below

2
On BEST ANSWER

These are all derivable from the same equality — they're all "the same sort of thing", to within permutation of arguments and renaming of variables.

Define $f_1(a,b,c) = f(a,c,b)$. Then $$\begin{align} g_1(x,y,z) &= \Sigma_{i=0}^z f_1(x,y,i)\quad\text{is p.r., but this equals} \\ &= \Sigma_{i=0}^z f(x,i, y) \\ &= h_1(x,z,y). \end{align}$$ So $h_1$ is p.r. Similarly, $h_2$ is p.r.