1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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$". $\endgroup$ – Random Jack Sep 4 '16 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.