I know that it's a bit stupid question.. , but still, Is there any difference between $RE$ and $RE\setminus R$ notations?

I'm asking because I saw that in some places using both of the notations, for example for $$ L_{HP}=\{(\langle M\rangle,x)|M\ halts\ on\ x\}$$

  • $\begingroup$ Please add explanation to negative vote in case it's mean something $\endgroup$ – ChaosPredictor Jan 26 at 16:41
  • 1
    $\begingroup$ My guess is that the downvotes are because there is no (or very few) research effort. You should think about the question first by yourself, if you do not succeed, try searching online for relevant questions and definitions. Only after, if you don't succeed at all, ask. $\endgroup$ – Bader Abu Radi Jan 29 at 8:16
  • $\begingroup$ Thank you @BaderAbuRadi, each time before I'm writing a new question I'm trying to solve it be myself and google it, Yes I know that I don't have enough background in logic and set theory, but for now I don't have time to fill the gap. I forced to take this course and I'm trying my best. To write a question, even if it's look a stupid one take time, I'm sure that even that most basic question can be asked, and may help some other users in the future as well. $\endgroup$ – ChaosPredictor Jan 29 at 18:04

$RE$ stands for recursively enumerable (recognizable) and $R$ for recursive (decidable). $RE\ \backslash\ R$ simply stands for all the sets that are are recursively enumerable, but not recursive (recall that every recursive set and its complement are recursively enumerable, but not every recursively enumerable set is recursive e.g. Halting Problem).

$R \subset RE$ and $L_{HP} \notin R$, therefore $L_{HP}$ can be in both $RE$ and $RE\ \backslash\ R$.

  • $\begingroup$ Thanks, I feel that my knowledge of logic is weak, your answer helped me. $\endgroup$ – ChaosPredictor Jan 26 at 16:45
  • $\begingroup$ Yes, your understanding (below) seems correct. Feel free to mark the answer as "accepted" if it helped! $\endgroup$ – MikeChav Jan 27 at 17:22

If I understood it right:

$$L_{HP}\in RE\setminus R$$

and because $$RE\setminus R\subset RE$$ So necessarily: $$L_{HP}\in RE$$

  • $\begingroup$ Any explanation to downvote? $\endgroup$ – ChaosPredictor Jan 29 at 17:53

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.