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

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 Answer

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.

-

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. – John Lee May 5 '12 at 22:27
$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. – William May 5 '12 at 22:53
Thank you very much. I really learned a lot from you. You are an amazing helper. – John Lee May 6 '12 at 5:14
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 57, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9201788902282715, "perplexity_flag": "head"}