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?


Your Answer

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

Browse other questions tagged or ask your own question.