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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.