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 $

  • 1
    $\begingroup$ What have you tried? Did you try to suggest a reduction? Where you got stuck? We can't just solve your exercises for you. $\endgroup$ Jan 27 at 20:03
  • $\begingroup$ 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 $\endgroup$
    – maya cohen
    Jan 27 at 20:06
  • 1
    $\begingroup$ You need to show some effort. Use the fact that $L$ is decidable, and the fact that HP is non-trivial. Proceed from there. $\endgroup$ Jan 27 at 20:07
  • $\begingroup$ 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? $\endgroup$
    – maya cohen
    Jan 27 at 20:13
  • 1
    $\begingroup$ "it looks like", in this case, try to prove that it is correct, and see how things go... $\endgroup$ Jan 27 at 20:37

1 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.

  • $\begingroup$ Oh i re-read this question and answer and I see that I didn't mention I was thinking it is a disproof , but from your answer I read you think I was understanding its a proof ... sorry for that ... $\endgroup$
    – maya cohen
    Feb 2 at 22:09
  • $\begingroup$ so if i understood correctly then I need to use the ability that regular languages are in R, and define a reduction that will do the same as what I said in my reduction? $\endgroup$
    – maya cohen
    Feb 2 at 22:10
  • 1
    $\begingroup$ Your reduction is not clear to me. If you want we can discus it in chat sometime. $\endgroup$ Feb 3 at 0:41
  • $\begingroup$ do you have time tommorow at 19:00 ? how can we have a chat in this website? $\endgroup$
    – maya cohen
    Feb 4 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.