# Prove that there is no computability reduction HP $\le$ $\Sigma$*

I tried to prove in negative way that there is computability reduction HP $$\le$$ $$\Sigma$$* and accept contradiction because of HP $$\in$$ RE and $$\Sigma$$* $$\in$$ R but it feels that is not strong argument.

There is a more solid way to prove it?

• What is "HP"? Halting problem? – dkaeae Jul 10 at 15:22
• @dkaeae Yes, its Halting problem – BizL Jul 10 at 15:24
• The argument is simple: To which string could you map the $\langle M_\bot, w \rangle$ when $M_\bot$ is a TM that never halts (i.e. a NO-instance for the halting problem)? – ttnick Jul 10 at 15:47
• @ttnick As far as I'm aware "computability" reduction is not well-used terminology, but I'm certain the OP is talking about Turing, not many-one reductions. – dkaeae Jul 10 at 16:38
• What is a "computability reduction"? – xskxzr Jul 11 at 3:52

Let us actually prove more: If $$L$$ is a language and $$L \not\in \mathsf{R}$$, then $$L \not\le_\mathrm{T} L'$$ for any $$L' \in \mathsf{R}$$. (Here, $$\le_\mathrm{T}$$ indicates a Turing reduction; this is synonymous with your notion of a "computability" reduction.) In other words, $$\mathsf{R}$$ is closed under Turing reductions.
Suppose towards a contradiction that such a reduction exists and is computed by a Turing machine $$M$$. Furthermore, let $$M'$$ be a decider for $$L'$$. Then there is a Turing machine which solves $$L$$, namely by directly simulating $$M$$, answering all of its oracle queries by simulating $$M'$$ on them, and, at the end, answering what $$M$$ does. This contradicts $$L \not\in \textsf{R}$$.
The case of the halting problem follows from it not being in $$\mathsf{R}$$ (since it is not even in $$\mathsf{RE}$$) and, naturally, $$\Sigma^\ast \in \mathsf{R}$$.
An aside: If you find the idea of classes closed under Turing reductions interesting, I suggest you look up the computation-theoretical notion of Turing degree. $$\mathsf{R}$$ would be the "base case" (i.e., degree zero) in that context.