By definition, a set $I \subseteq \mathbb{N} $ is an index set if $\forall i,j ((i \in I \land \varphi_i = \varphi_j) \implies j \in I)$.
Thanks to the Rice's Theorem, we know that, said $F$ a family of partial computable functions on the naturals, the set of their code $E = \{e \in \mathbb{N} | \varphi_e \in F\}$ is not-computable unless is empty or equal to the set of the codes of all partial computable functions.
As reported in the title, my question is: is there a set of indexes that is computably-enumerable but is not Turing equivalent to the Halting Set $H = \{ h \in \mathbb{N} | \varphi_h(h) \downarrow\}$?
I tried considering for example the set of codes $A = \{ a \in \mathbb{N} | \operatorname{dom}(\varphi_a) \neq \emptyset \} $ but it is many-one equivalent to the Halting Set (and hence Turing equivalent). Do you have any suggestion?
Best Answer
No. This is because any non trivial index set must compute the halting problem, and the only c.e. sets that compute the halting problem are Turing equivalent to it.
Let $I\subseteq\mathbb{N}$ be a non trivial index set. Either $I$ or $\mathbb{N}\setminus I$ contains the indices for the empty function, that is the function that at any input does not halt. Since $I=_T\mathbb{N}\setminus I$ we may assume without loss of generality that $I\setminus \mathbb{N}$ contains the indices for the empty function. Let $i\in I$ be any index. Consider the partial computable function $f$ given by: \begin{equation*} f(e,x)=\begin{cases} \Phi_i(x)\quad \text{ if }\quad \Phi_e(e) \downarrow\\ \text{ doesn't halt otherwise } \end{cases} \end{equation*} The function waits to see if $\Phi_e(e)\downarrow$ halts, if it does it starts computing $\Phi_i(x)$, which may or may not halt. By the smn theorem there is a primitive recursive function $s$ such that $f(e,x)=\Phi_{s(e)}(x)$. We note that if $\Phi_e(e)\downarrow$ then $\forall x\; f(e,x)=\Phi_{s(e)}(x)=\Phi_i(x)$ and so $s(e)\in I$ and if $\Phi_e(e)\uparrow $ then $\forall x\; f(e,x)\uparrow$ and so $s(e)\in \mathbb{N}\setminus I$. So we can compute the halting problem from $I$ by checking if $s(e)\in I$ or not. In fact if we take $s$ to be injective, which is possible using padding, we showed that $\{e:\Phi_e(e)\downarrow\}\leq_1 I$.