2

The Recursion theorem states that if $f$ is a (total) computable function, then $f$ has a fixed point in the sense that there exists an $e$ such that $\varphi_e = \varphi_{f(e)}$. I have the following corollary to the Recursion theorem which I can't seem to prove.

If $f(x,y)$ is a computable function, then there exists an index $e$ such that $\varphi_e(x) = f(e,y).$

I think we need to use the $S^m_n$ theorem to construct a function depending on $f$ on which we can apply the recursion theorem (i.e. a computable function $g$ such that $\varphi_{g(e)}(y) = f(e,y)$) but I am not sure how to do this. Any help is appreciated.

user151850
  • 87

1 Answers1

1

The function $g$ you propose exists via the $S^m_n$ theorem:

you have a code $e$ such that

$\varphi_e(x,y) = f(x,y)$

By the $S^m_n$ theorem you have a computable function $S$ such that:

$\varphi_{S(e,x)}(y) = \varphi_e(x,y)$

But $e$ is then a constant parameter for what you need. You can just define the computable function $g(x)$ to be $S(e,x)$.

Archimondain
  • 918