Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 0 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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