A Question About Recursive Functions

40 Views Asked by At

We want to find a recursive function $f(x,y)$ in order to have this equality:

$$ \mathbf \varphi_{f(x,y)} = \varphi_x + \varphi_y$$

I know we should use "s-m-n" theorem, but I can't find the required function.
We be grateful for your help.

1

There are 1 best solutions below

2
On BEST ANSWER

Consider the universel program $U(x,y)=\phi_x (y)$

From U, there is a program $\phi_p(x,y,z)=U(x,z)+U(y,z)$

Now, consider $f(x,y)=s_1^2(p,x,y)$ $$\forall z \quad\phi_{f(x,y)}(z)=\phi_p(x,y,z)=\phi_x (z)+\phi_y(z)$$