0
$\begingroup$

question is as written in the title:

show that there is no partial recursive function f s.t. whenever N-W_e has one element, f converges and N-W_e = {f(e)}.

W_e is the domain of the program coded by e. So if there is a converging function f such that f(e) = N-W_e, how do I get a contradiction?

1 Answers 1

0

There exists a computable function $g$ such that $\Phi_{g(e)}(s) = \begin{cases} 1 & \quad \text{ if $s > 0$ and $\Phi_{e,s}(e)\uparrow$} \\ 1 & \quad \text{ if $s = 0$ and $(\exists t)(\Phi_{e,t}(e)\downarrow$)} \\ 1 & \quad \text{ if $(\exists t < s)(\Phi_{e,t}(e)\downarrow$)} \\ \uparrow & \quad \text{ otherwise} \end{cases}$ where $\uparrow$ means diverging computation and $\downarrow$ means converging computation. Note $\Phi_{e,s}(e)$ means the computation up to $s$ stages. Note that if $\Phi_{e}(e)$ converges then the only divergence occurs on the smallest $s$ that $\Phi_{e,s}(e)\downarrow$. If $\Phi_{e}(e)$ does not converges, then the only element that does not converge is $0$.

Intuitively, $W_{g(e)} = \omega - \{0\}$ if $\Phi_{e}(e)\uparrow$. If $\Phi_{e}(e) \downarrow$, then $W_{g(e)} = \omega - \{t\}$ for some $t > 0$ (not relevant but this $t$ is the smallest stage for which the computation converges). Note that by construction $W_{g(e)}$ is always missing exactly one element.

Even better intuition: As long as $\Phi_{e,s}(e)$ diverges on stage $s > 0$, enumerate s into $W_{g(e)}$. For the first state $t$ (if it exists) such that $\Phi_{e,t}(e)\downarrow$, then enumerate $0$ into $W_{g(e)}$, do not ever enumerate $t$ into $W_{g(e)}$ and enumerate everything bigger than $t$. So if $\Phi_{e}(e)$ diverges, then $W_{g(e)}$ is missing only $0$. If $\Phi_{e}(e)$ converges, then $W_{g(e)}$ is missing only some $t > 0$.

Assume that $f$ exists. Let $K = \emptyset' = \{e : \Phi_{e}(e)\downarrow\}$. Therefore, $e \in \bar{K}$ if and only if $0 \in \omega - W_{g(e)}$ if and only if $f(g(e)) = 0$. Since $W_{g(e)}$ is always missing exactly one element, $f(g(e))$ is a total function. Therefore $\bar{K}$ is computable. Contradiction. Since $\bar{K}$ is actually not even c.e.

  • 0
    Thank you very much. I really learned a lot from you. You are an amazing helper.2012-05-06