Are the sets

a) $\{x | \exists y \phi_x(y) = 0\}$

b) $\{x | \phi_x(5) \uparrow \land x \leq 5\}$

recursive, recursively enumerable (r.e.) or none of them? Please explain your solution.

$\phi_x$ is the xth computable function.

Hint: The tools that are available are Rice's theorem, dovetailing, diagonalization, s-n-m...

If we apply Rice's theorem to the first one I don't think it is enumerable since the set is $\neq \emptyset $ and $\neq \mathcal{N}$. But, I think it could be r.e. if we use the dovetailing technique.

For the second one we only have to check the first 6 computable functions, but the $x$ is in the set if $\phi_x$ diverges. This would mean we use the following function to determine whether x is in the set $$ g(x) = \left\{ \begin{array}{l l} 1 & \quad \text{if $\phi_x(5) \uparrow$ }\\ 0 & \quad \text{otherwise} \end{array} \right. $$ but this function is not computable (halting problem). Therefore it is not recursive nor r.e.?

Do you agree with all this and how would you answer this using semantics and formal arguments?


You're right, the first set is r.e. It's not recursive by Rice theorem and is enumerable by dovetailing.

The second one is recursive, because it's finite. Any finite set is recursive. It doesn't mean that you know how you can compute it, but it means there is for sure a function that computes it.

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