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

Is there a slick way to define a partial computable function $f$ so that $f(e) \in W_{e}$ whenever $W_{e} \neq \emptyset$? (Here $W_{e}$ denotes the $e^{\text{th}}$ c.e. set.) My only solution is to start by defining $g(e) = \mu s [W_{e,s} \neq \emptyset]$, where $W_{e,s}$ denotes the $s^{\text{th}}$ finite approximation to $W_{e}$, and then set $$ f(e) = \begin{cases} \mu y [y \in W_{e, g(e)}] &\text{if } W_{e} \neq \emptyset \\ \uparrow &\text{otherwise}, \end{cases} $$ but this is ugly (and hence not slick).

share|cite|improve this question
@Quinn: Your approach looks clean and natural, more or less the opposite of ugly. – André Nicolas May 27 '11 at 20:43
@user6312 Ya, I should pin down exactly why I think my approach is ugly. I was hoping that someone would present a slick(er) solution that would make this clear. – Quinn Culver May 27 '11 at 20:48
I agree - implicitly the only think you can do is wait until the process that generates $W_e$ actually enumerates something, and, since it might never enumerate another element, you really can almost only choose $f(e)$ as, in some sense, the "first" element of $W_e$ which gets enumerated. If $W_{e,s+1}-W_{e,s}$ can have cardinality greater than $1$, you need some way to select an element of the difference, and $\mu$ is the easiest way to do so. – Thomas Andrews May 27 '11 at 20:51
I would add that the definition of $f(e)$ should probably actually be: "If $g(e)\downarrow$," rather than "If $W_e\neq \emptyset$" to be effective. – Thomas Andrews May 27 '11 at 20:54
@Quinn: Well, you could do something much more complicated, but (1) It has to do the right thing when $W_e$ is a singleton. (2) The set of $e$ such that $W_e$ is a singleton is not r.e. (3) So, impliclty, any $f(e)$ solving your problem is going to have the property that for infinitely many $e$, $f(e)\downarrow$, $f(e)$ is the first enumerated element of $W_e$ and $W_e$ is not a singleton. – Thomas Andrews May 27 '11 at 21:51
up vote 2 down vote accepted

I can at least show you how to get that down to one use of the $\mu$ operator. Based on the response to my comment above this might be what you want.

Following your construction in sprit, let $h$ perform the following computation on input $e$. It computes $\phi_e(0)$ for one step; then $\phi_e(0)$ and $\phi_e(1)$ for two steps each; then $\phi_e(0)$, $\phi_e(1)$, and $\phi_e(2)$ for three steps each; and so on. During this computation, if it ever happens that we see $\phi_e(i)$ converge to some number $j$, we let $h(e)$ return $j$. Otherwise, if $\phi_e(n)$ never converges for any $n$, $h(e)$ will be undefined. So $h(e) \in W_e$ whenever $W_e$ is nonempty, because $W_e$ is defined as the range of $\phi_e$.

Because $h$ is computable, it has some index $l$. Let $$ f(e) = U(\mu s.T(l, e, s)) $$ where $T$ and $U$ are Kleene's functions (as in [1]). In fact we have $f \simeq h$ by the definition of these functions. This is what I meant when I said in my comment that your construction is almost an equational definition of $f$.


share|cite|improve this answer

Perhaps the reason your solution seems ugly to you is that you appear to be excessively concerned with the formalism of representing your computable function in terms of the $\mu$ operator. The essence of computability, however, does not lie with this formalism, but rather with the idea of a computable procedure. It is much easier and more enlightening to see that a function is computable simply by describing an algorithm that computes it, and such kind of arguments are pervasive in computability theory. (One can view them philosophically as instances of the Church-Turing thesis.)

The set $W_e$ consists of the numbers that are eventually accepted by program $e$. These are the computabley enumerable sets, in the sense that there is a uniform computable procedure to enumerate their elements.

We may now define the desired function $f$ by the following computable procedure: on input $e$, start enumerating $W_e$. When the first element appears, call it $f(e)$.

It is now clear both that $f$ is computable and that $f(e)\in W_e$ whenever $W_e$ is not empty, as desired.

share|cite|improve this answer

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.