Search code examples
computation-theorydecidable

Is there a non-RE language that is composed of only 1 element?

I read in a book (Hromkovic, Communication Complexity and Parallel Computating) that there is an infinite number of non recursively - enumerable (non-RE) languages that are composed of only 1 element? But is that possible? I though that for a language to be non-RE (or even undecidable), the language has to be infinite.

Solution

  • No, all finite languages are regular because they can be accepted by finite automata. There are at least three possible explanations for what you read:

    1. the author(s) wrote something different and you are paraphrasing incorrectly;
    2. the author(s) wrote something other than what they intended, possibly using sloppy terminology;
    3. the author(s) wrote something incorrect due to a misunderstanding of subject matter not belonging to their specialty.

    If you quote the relevant passage, it might be possible to explore which of these options is most likely. Note that everybody makes mistakes - people who read books and people who write books alike. Note also that I use author(s) and not authors because it's possible this passage was written in isolation by one author and was not properly reviewed.