# Finding a suitable function to use Kleene's recursion theorem

Problem. Suppose $g(x)$ is a partial recursive function such that for all $e$, $$W_e = \varnothing \Longrightarrow g(e)\!\downarrow .$$ Prove that there is some $m$ such that $$W_m = \{m\} \text{ and } g(m)\!\downarrow.$$

What I've tried so far is the following. Consider the function $$f(m, x) = \begin{cases} 1, \text{ if g(m) converges in exactly x steps},\\ \uparrow, \text{ otherwise. } \end{cases}$$ By the recursion theorem there is some $m$ such that $\varphi_m(x) = f(m, x)$. If $g(m)\!\uparrow$, then $W_m = \varnothing$ and hence, by the assumption, $g(m)\!\downarrow$. It means that $g(m)\!\downarrow$ and for some $x$ we have $W_m = \{x\}$.

I tried to use some variations of $f(m, x)$ like the following: $$f(m, x) = \begin{cases} \varphi_{e_0}(m, x), \text{ if g(m) converges in at most x steps},\\ \uparrow, \text{ otherwise, } \end{cases}$$ where $\varphi_{e_0}(m, x)\!\downarrow \Longleftrightarrow m = x$. After applying the recursion theorem, if $g(m)\!\uparrow$, then again $W_m = \varnothing$ and hence $g(m)\!\downarrow$. Then $g(m)$ converges in exactly $x_0$ steps for some $x_0$ and $$\varphi_m(x) = \begin{cases} \varphi_{e_0}(m, x), \text{ if x \geqslant x_0},\\ \uparrow, \text{ otherwise. } \end{cases}$$ If $m \geqslant x_0$ then $W_m = \{m\}$, otherwise $W_m = \varnothing$. I know that there are infinitely many fixed points, but that doesn't help since for each such $m$ we still can have $m < x_0$.

So, probably this approach is flawed. I don't understand how to combine the information about the convergence of $g(m)$ and $m$ itself to get a suitable function $f(m, x)$.

Question. Can you give me some hint for finding such a function?

## 1 Answer

Let $f(m,x)=1$ if $m=x$ and $g(m)$ converges; otherwise diverge. This is computable, since on input $(m,x)$, we simply compute $g(m)$, and if it halts then check if $x=m$ or not.

Spoiler: By the recursion theorem, there is $m$ with $\varphi_m(x)=f(m,x)$. If $W_m$ is empty, it means that $g(m)\downarrow$, as you observed, and in this case we'll have $m\in W_m$, a contradiction. So $W_m$ is not empty. But by the definition of $f(m,\cdot)$, the only possible element of $W_m$ is $x=m$ itself, so $W_m=\{m\}$, and this occurs only when also $g(m)\downarrow$.

• Thank you, Mr. Hamkins! That was easier than I thought - there was no need to care about the number of steps at all and to use recursive relation "$g(m)$ converges in $x$ steps" rather than recursively enumerable "$g(m)$ converges and $m = x$". – Random Jack Sep 4 '16 at 20:06