1
$\begingroup$

I want to check if I understood it in the right way. In some example where $L\in RE$ the explanation deal with 2 cases: 1st when $L$ finite and 2nd when $L$ infinite. In the second case $L\in R$, isn't? Is it possible somehow that $L\in RE\setminus R$ be finite?

$\endgroup$
4
  • 1
    $\begingroup$ The question is unclear to me. For example, I don't understand what you mean by "The second case is 𝐿∈𝑅, isn't?". Regarding the last question, every finite language is regular and thus decidable. $\endgroup$ Jan 15 at 19:49
  • $\begingroup$ Thanks @BaderAbuRadi, I edited the question is it clear now? $\endgroup$ Jan 15 at 19:58
  • $\begingroup$ Sorry, it is still unclear. Are you asking: 1) whether every infinite recognizable language $L$ is in $R$? 2) whether there are finite languages in $RE\setminus R$? $\endgroup$ Jan 15 at 20:22
  • $\begingroup$ Whether there are finite languages in 𝑅𝐸∖𝑅? $\endgroup$ Jan 15 at 20:25
1
$\begingroup$

The answer is no. Every finite language is regular, and thus decidable. Therefore the existence of a finite language $L$ in $ \text{RE} \setminus \text{R}$ is impossible. However, note that there languages $L$ in $\text{RE}\setminus \text{R}$ (e.g., $Halt_{TM}$), and by what we have seen previously, such languages have to be infinite.

$\endgroup$

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.