Proof or Disproof if $ L $ is a Regular language then it has to be that $ L\leq HP $

Question

Proof or Disproof

if $ L $ is a Regular language then it has to be that $ L\leq HP $

$ HP=\{<M,x> | M \ halts \ on \ x \} $ Regular language is a language that can be expressed with a regular expression or a deterministic or non-deterministic finite automata

I know that HP is in RE\R and I know the regular language is in R and I know that due to the reduction principle, if $ L1 \leq L2 $ then if $ L2 \in RE $ then L1 must also be in RE and also if L1 is not in RE then L2 also not in RE but this is not the case...

$ f(x) = <M',x> $ lets create M' such that for all x $in \Sigma^* $

1. run $ M_{regular} $ on x if accepts then accepts
2. if rejects then go to infinite loop

L is a decidable language then exist a decidable turning machine such that for all x will halt

HP will only halt on x in the language,

if I try to build a reduction from L to HP lets look at the conditions

$x\in L \rightarrow M_L(x)=1 \rightarrow $ M halt on x $ <M',x> \in HP $

$x\notin L \rightarrow M_L(x)=0 \rightarrow $ I can send here to an infinite loop so that M doesn't halt on x $ <M',x> \notin HP $

Answer 1

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 a slightly more general claim, specifically, every non-trivial language is $R$-hard (harder than every language in $R$). Since $L\in R$, and $HP$ is non-trivial, then what you're asking for 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. So languages in $R$ are too easy, w.r.t mapping reductions, in the sense that we (the reduction) can solve/decide them, and then output whatever we want.