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$ 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

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.


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.