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.