0
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.