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?
$\begingroup$
$\endgroup$
7
-
$\begingroup$ What is "HP"? Halting problem? $\endgroup$ – dkaeae Jul 10 '19 at 15:22
-
$\begingroup$ @dkaeae Yes, its Halting problem $\endgroup$ – BizL Jul 10 '19 at 15:24
-
3$\begingroup$ 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)? $\endgroup$ – ttnick Jul 10 '19 at 15:47
-
2$\begingroup$ @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. $\endgroup$ – dkaeae Jul 10 '19 at 16:38
-
1$\begingroup$ What is a "computability reduction"? $\endgroup$ – xskxzr Jul 11 '19 at 3:52
|
Show 2 more comments
$\begingroup$
$\endgroup$
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.
