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
    Would you be so kind as to explain what K and K-overscore are? I didn't understand the last part on why f(g(e)) is a total function and why K-overscore is not c.e.2012-05-05
  • 0
    $k = \emptyset' = \{e : \Phi_e(e)\downarrow\}$, i.e. the halting set.$\overline{K}$ is the complement of $K$. It is well known that $K$ is not computable but c.e. If $\overline{K}$ was c.e.,then $K$ and $\bar{K}$ is c.e. so $K$ would be computable. Note that only the fact that $\bar{K}$ is not computable is necessary for the proof. By the discussion above, $W_{g(e)}$ always missing exactly 1 element for any $e$. By assumption, whenever $W_x$ is missing exactly one element $f(x)$ is defined and $\omega - W_x = \{f(x)\}$. Hence $f(g(e))$ is total.2012-05-05
  • 0
    Thank you very much. I really learned a lot from you. You are an amazing helper.2012-05-06