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?

$\endgroup$
1
  • $\begingroup$ What does it mean for a Turing machine to "generate" a language? Turing machines normally accept or decide languages. $\endgroup$ Dec 17, 2014 at 8:29

1 Answer 1

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.

$\endgroup$
2
  • 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$ Dec 18, 2014 at 7:51
  • 1
    $\begingroup$ Right. But in this context the alphabet is always assumed to be finite. $\endgroup$ Dec 18, 2014 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.