Since strings are finite by definition, then it follows that languages are enumerable because they are finite string sets and we know that finite string sets are enumerable. Turing Machines are enumerable, because each Turing Machine has a finite string description. Therefore:

  1. If all languages are enumerable, and we know that if there is an enumerator (which is also a Turing Machine) then the language is recognizable, then all languages are recognizable.
  2. If Turing Machines are enumerable and languages are enumerable, we can have a bijection between Turing Machines and languages.
  3. If Turing Machines are enumerable and languages are innumerable, we conclude that all languages are recognizable because each language has an associated Turing Machine (and enumerator).

Where are the errors of this question? Item 1? Item 2? Item 3?? Explain each of the alternatives, even it is correct.


1 Answer 1


Your sentence "languages are enumerable" could be ambigous.

A given language is enumerable, because it is a set of finite strings, but the set of languages is not enumerable, because it is the powerset of an infinite set ($\Sigma^*$).

That means that all your 3 items are false.

  • $\begingroup$ Thanks for the answer. The first part of the question is a definition. You have to assume it's true. The statements must be validated. Could you explain why all three are false, commenting one by one? $\endgroup$ Commented Oct 19, 2022 at 12:35
  • 4
    $\begingroup$ Well, no, please use my answer as an indication to find the answers yourself (otherwise there is no point to the exercise). $\endgroup$
    – Nathaniel
    Commented Oct 19, 2022 at 13:05

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.