Def. A set A is recursively enumerable if $A = \emptyset$ or if there exists a total computable function $g$ such that $A = R(g)= \{z | \exists x. g(x) = z \}$.
Def. A set A is semi-decidable if there exists a computable function f such that $f(x) = 1 \text{ if } x \in A \text{ and} \uparrow \text{otherwise}$.
Proof: Assume a set I is semi-decidable, show that I is recursively enumerable as well:
If $I = \emptyset$, then I is r.e. by definition.
If $I \not= \emptyset$, then $\exists k.k \in I$. By assumption, there exists the partial computable function $h$ that decides whether an element is in $I$ for positive cases. We construct the following algorithm, where $y$ is the coding of the pair of natural numbers $(x, n)$.
$$g(y) = d(x, n) = x \text{ if } h(x) \downarrow \text{in } n \text{ steps, and } k \text{ otherwise.}$$
This is how the proof was presented in class. The result is pretty clear to me, but I don't understand why we can use $k$ in the algorithm. We assume that some $k$ exists, and that we can output that whenever some $h(x)$ does not halt. It's obvious that such $k$ must exist since $I \not= \emptyset$, but can we use it? If we have already found some x for which $h(x)$ halts, then we can just return that $x$ as $k$. But what do we return if we haven't found that x yet?
I think that to find $k$ is almost as difficult as to solve this problem. To complete this proof, we can find $k$ this way:
Notation: $p(y) = x, q(y) = n$ if $y$ is the code of $(x, n)$, (assuming the decoding function is total, which could be guaranteed by a concrete encoding scheme).
Let $$ N = \mu y [h(p(y)) \downarrow \text{ within $q(y)$ steps }]$$ Then we can choose $$k = p(N)$$
Note that $N$ is defined for $I \ne \emptyset$.