Assume $\mathcal{K}$ is the set of all partial computable functions $f: \omega \rightarrow \omega$ such that $\vert \{x:f(x)=0\}\vert \leq 2$.
I want to prove that the index set $I=\{k\in\omega:\varphi_k\in\mathcal{K}\}$ is neither computable nor is it computably enumerable.
Obviously $\mathcal{K}$ is neither empty nor is it the set of all partial computable functions. From Rice's Theorem follows that $I$ is not computable.
I think it is clear for me why $I$ is not c.e.: There has to be a computable function which enumerates $I$. So in terms of a Turing machine I would have to translate each index to a partial computable function and then count if $0$ does not occure more then two times in the range of these functions. This is impossible because the functions are partial, hence when we evaluate each function and count the $0$'s we cannot avoid trying to evaluate the function at a point where it is not defined. Therefore by trying to evaluate it at such a point would mean that the machine doesn't terminate although the function could be still in $\mathcal{K}$. I would like to prove this in a more formal way. I have thought about an diagonalisation argument since this seems to be a good approach for showing that a set is not c.e., but I haven't found one yet.
Another approach was to show that $I$ is not in $\Sigma_1^0$:
$$i\in I \Leftrightarrow \exists x ~\exists y ~\forall z~[(x\neq z\land y\neq z) \Rightarrow \varphi_i(z)\neq0]$$
But I can't show that this proposition is not equivalent to an element in $\Sigma_1^0$.
Best Answer
As you note, by Rice's theorem $I$ cannot be $\Delta^0_1$. So it would be enough to prove that $I$ is $\Pi^0_1$. This can be done by writing out the definition carefully, but it might be easier to work with the complement $$I^c=\{k:\varphi_k\not\in\mathcal{K}\}=\{k:\vert\{x:\varphi_k(x)\downarrow=0\}\vert>2\}.$$ (Here "$\downarrow=$" means "is defined and is equal to.")
That is, $I^c$ is the set of $k$ such that there are distinct $a,b,c$ with $\varphi_k(a),\varphi_k(b),$ and $\varphi_k(c)$ are each defined and equal to $0$. This is clearly $\Sigma^0_1$ (the key point being that "is defined" is a $\Sigma^0_1$ property).
Or, thinking in terms of computations and Church's thesis, we can see that $I^c$ is c.e. (and hence $I$ must not be c.e. since $I$ is noncomputable) by thinking about "dovetailing" the infinitely many computations $\varphi_k(a)$ $(a\in\mathbb{N}$) and halting iff we see at least three of these halt.