Skip to main content
1 of 3
Bader Abu Radi
  • 4.9k
  • 1
  • 11
  • 38

From your attempt, I see that you got the intuition, but you need to define the reduction formally, and then prove that it works. In your solution, it is not clear how $M'$ is defined, and what is $M_{regular}$ -- for me, I just saw your thoughts/attempts, not a proof.

Here, I showed that every non-trivial language is $R$-hard, that is, harder than every language in $R$. Since $L\in R$, and $HP$ is non-trivial, what you're asking follows immediately. Try to prove that the reduction there is computable (there is a TM that computes it), and that it is correct.

The idea essentially is as follows. Since we can decide $L$, then we can define a reduction that checks whether its input is in $L$, and then outputs a word inside or outside $HP$, accordingly.

Bader Abu Radi
  • 4.9k
  • 1
  • 11
  • 38