# Showing $1$-reducibility of $\overline{\text{HALT}'}$ to index set

Note: overline denotes complement

I am trying to show that $\overline{\text{HALT}'}\leq_1 \{i\colon\Phi_i=\Phi_e\}:= A$ for some fixed $e$ but I am misunderstanding the problem or method and can't figure out where I'm going wrong. I am using the construction of the proof of Rice's theorem to prove this and I thus do the following:

Let $e_0\colon \Phi_{e_0}\uparrow$. We thus have that, as long as $\Phi_e\downarrow$, $e_0\in\overline{A}$. Now choose $e_1\in A$ and define $s$ such that $$\Phi_{s(x)}(y) = \begin{cases} \Phi_{e_1}(y),& \text{if } x \in \text{HALT},\\ \text{undefined},& \text{if } x\not\in \text{HALT} \end{cases}$$ we thus get that $x\in\text{HALT}\implies s(x)\in A$ while $x\not\in\text{HALT}\implies s(x)\in\overline{A}$ and it follows that $\text{HALT}\leq_1 A$ and $\overline{\text{HALT}}\leq_1\overline{A}$.

This is, however, the opposite of what I want but I can't seem to see where I'm going wrong? Any help would be greatly appreciated!

## 1 Answer

Let $e$ be and index for the constant 0 function. Then consider $s$ such that

$$\varphi_{s(x)}(y) = \begin{cases} 0 & \mbox{ if }\varphi_x(x) \mbox{ does not halt within y steps} \\ 1 & \mbox{otherwise} \end{cases}$$

Then $\varphi_{s(x)} = \varphi_e$ if and only if $x \not\in HALT$ (assuming HALT was the diagonal halting problem).

The function $s$ can be choosed to be monotonic (use pumping), hence it is one-to-one.