# Are these sets recursive, r.e. or none

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?