I have a set $S$, where $x \in S$ is semidecidable, i.e. there is a function $f(\cdot)$ that returns 1 in finite time if $x \in S$ but will not halt if $x \notin S$*. I also have an effective enumeration $A_0, A_1, \dots$ of $A$, where $S \subset A$. Is there a way to effectively enumerate $S$?
Thanks for your help! Best, Leon
*Alternatively, I have effectively decidable functions $f_1(\cdot), f_2(\cdot), \dots$ s.t. $x \in S$ iff there is an $n$ s.t. $f_n(x) = 1$.
Start enumerating the $A_i$ using your given effective method. Interweaved with that [when you have got to $A_1$ in this first enumeration] do a couple of steps on the computation of $f(A_0)$, then a step of work computing $f(A_1)$. Then [when you have got to $A_2$ in the first enumeration] do another step computing $f(A_0)$, another step on $f(A_1)$, and a first step on $f(A_2)$. Then [when you have got to $A_3$ in the first enumeration] do another step on $f(A_0)$, $f(A_1)$, and $f(A_2)$ and a first step on $f(A_3)$. Keep on going.
Whenever one of the intermittent computations of $f(A_j)$ halts with output 1, put down this $A_j$ on your growing list of members of $S$.
Eventually any member of $S$ will be listed. Voilà! Your effective enumeration of $S$.
Comment This kind of interweaving of computations is an absolutely basic technique for proving elementary results in the theory of effective computability. Check your textbook for other examples!