Slick way to define p.c. $f$ so that $f(e) \in W_{e}$

Question

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).

Answer 1

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$.

1: http://en.wikipedia.org/wiki/Kleene%27s_T_predicate

Answer 2

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.