2
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.