# Question about Proof: Semi-decidable => Recursively Enumerable

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?

## 1 Answer

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