1
$\begingroup$

Are all languages generate by Turing machines countable? I know that the set of all TMs are countable, but what about the languages that they generate?

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ What does it mean for a Turing machine to "generate" a language? Turing machines normally accept or decide languages. $\endgroup$ – David Richerby Dec 17 '14 at 8:29
2
$\begingroup$

Yes. All languages, not only those generated by Turing machines, are countable. This is because they are all subsets of $\Sigma^*$, and $\Sigma^*$ itself is countable. However, there are uncountably many languages.

| cite | improve this answer | | | | |
$\endgroup$
  • 1
    $\begingroup$ Not all languages are countable e.g. for language of first order logic one sometimes add constants denoting every element. If such language describes real nunbers then such language is uncountable. $\endgroup$ – Trismegistos Dec 18 '14 at 7:51
  • 1
    $\begingroup$ Right. But in this context the alphabet is always assumed to be finite. $\endgroup$ – Yuval Filmus Dec 18 '14 at 8:16

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.