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

Proof or Disproof

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

$$HP=\{ | 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) = $$ 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 $$ \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 $$ \notin HP$$

• What have you tried? Did you try to suggest a reduction? Where you got stuck? We can't just solve your exercises for you. Jan 27 at 20:03
• I ask for help this is why I am stuck, from my knowledge I don't know what to do because all the Data in the question does not help me, and I do not understand how to continue because the reduction principle doesn't fit here Jan 27 at 20:06
• You need to show some effort. Use the fact that $L$ is decidable, and the fact that HP is non-trivial. Proceed from there. Jan 27 at 20:07
• Hey @BaderAbuRadi I added what I tried but with what I think but then it looks like the reduction is valid what I did wrong? Jan 27 at 20:13
• "it looks like", in this case, try to prove that it is correct, and see how things go... Jan 27 at 20:37

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.